

pythonを最近学習し始めた者です。  
pythonを使用してやりたいことがあるのですが、キーワードがわからない為、やり方を検索できずにいます。

以下やりたい内容となります。

やりたいこと：ある地域の中に３つのタクシー会社があるとします。（会社A・会社B・会社C）各会社の所有タクシー数は、[会社A：２台][会社B：２台][会社C：１台]  
タクシーを呼ぶ人は地域内の建物にいることとし、タクシー会社から地域内の各建物までの距離はあらかじめ別のcsvファイルで作成してあります。  
タクシーを呼ぶ人がいた時、タクシーを呼んだ人がいる建物に近い会社からタクシーを配車させることを繰り返した時に、タクシーがすべて出払っている会社が出るといった事象が起きることが考えられますが、そういった場合に、タクシーを呼んだ人のいる建物から近く、タクシーの残っている会社からタクシーを配車する場合にはpythonのどのような機能を使用すればよいでしょうか。  
３つの会社のタクシー数＜タクシーを呼ぶ人の数  
とし、全タクシー会社のタクシーがすべて配車されるまで繰り返すものとします。

このような内容をpythonで構築したい場合、どのようなキーワードで検索、どのような構文で構築するのが良いのでしょうか。  
初歩的なことをお聞きし申し訳ございませんが、よろしくお願いいたします。


CC BY-SA 4.0
2019-10-27T10:45:44.807
60013
2020-04-08T06:00:55.113
2019-10-27T17:11:45.523
19110
36305
question
python アルゴリズム
python 配車問題


恐らく、「クラス」や「オブジェクト指向」について勉強すると良いと思います。

「Python クラス 使い方」などで検索しましょう。

Daaaaai39さんのやりたいことは、タクシー会社A、タクシー会社B、タクシー会社Cという「クラス」を作る（正確には、タクシー会社クラスを作り、A,B,Cそれぞれの会社の値で初期化して使う）ことで、非常に分かりやすく、応用できる形で解けるようになります。

恐らく蛇足だと思いますが、他には二次元ベクトルの計算が必要なので、「二次元ベクトル
距離」等での検索もされると良いでしょう。このような計算は、メソッドとしてクラスに実装すると良いです。


CC BY-SA 4.0
2019-10-28T16:42:00.703
60049
2019-10-28T16:49:50.877
2019-10-28T16:49:50.877
8795
8795
60013
answer


アルゴリズムとしては、[貪欲法](https://ja.wikipedia.org/wiki/%E8%B2%AA%E6%AC%B2%E6%B3%95)で配車問題を解きたいという話だと感じました。

具体的には、次のように問題を抽象化して：

[code]

    resource[i] : 会社 i の所有タクシー数
    cost[i][j] : 建物 i から会社 j までの距離
    jobs[i] : i 番目の呼び出しで呼ばれた先の建物
    
[/code]

これに対し「タクシーが残っている会社 (`cost[i][j] > 0` な会社 `j`) の中で距離が最短の会社 (`cost[job[i]][j]`
が最小の会社 `j`) 」を順番に割り当てていく手順です。

疑似的にプログラムを書くとこのような感じです：

[code]

    result = [-1] * len(jobs)
    for i, job in enumerate(jobs):
        # 最短の会社を見つける
        nearest = -1
        min_cost = float("inf")
        for company, r in enumerate(resource):
            if r > 0 and cost[job][company] < min_cost:
                nearest = company
                min_cost = cost[job][company]
        if nearest == -1:
            # もうタクシーが残っていない
            break
        # 見つけた会社に割り振る
        resource[nearest] -= 1
        result[i] = nearest
    
[/code]


CC BY-SA 4.0
2019-10-28T17:12:32.270
60050
2019-10-28T17:12:32.270
19110
60013
answer