質問編集履歴

コードの追記

2017/03/05 11:13

投稿

okazujet

スコア11

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -72,8 +72,290 @@
 不明瞭な点があれば質問をお願いします。
-###補足情報(言語/FW/ツール等のバージョンなど
-python
+```python
+# -*- coding: utf-8 -*-
+import math
+import itertools
+import queue
+import numpy as np
+import csv
+def compute_travel_time_between2shops(shop1, shop2):
+    start_node = ""
+    goal_node = ""
+    shop1_node_distance = 0
+    shop2_node_distance = 0
+    #shop1とshop2には，Nodeも許すので，条件分岐する
+    if isinstance(shop1, Node) and isinstance(shop2, Node):
+        start_node = shop1
+        goal_node = shop2
+    elif isinstance(shop1, Node):
+        start_node = shop1
+        goal_node = shop2.node
+        shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2)
+    elif isinstance(shop2, Node):
+        start_node = shop1.node
+        goal_node = shop2
+        shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2)
+    else:
+        start_node = shop1.node
+        goal_node = shop2.node
+        shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2)
+        shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2)
+    result_time = shop1_node_distance + shop2_node_distance
+    if start_node == goal_node:
+        return result_time
+    searched_nodes = []
+    unsearched_nodes = []
+    start_node = Neo_Node(start_node)
+    unsearched_nodes.append(start_node)
+    while True:
+        if len(unsearched_nodes) == 0:
+            break
+        #確定nodeを一つ決める
+        done_node = ""
+        temp_cost = 100000
+        for un_n in unsearched_nodes:
+            if un_n.cost < temp_cost:
+                done_node = un_n
+                temp_cost = un_n.cost
+        #決まったら入れ替え
+        searched_nodes.append(done_node)
+        unsearched_nodes.remove(done_node)
+        #done_nodeに繋がるnodeを未確定に入れる
+        for (edge, cost) in zip(done_node.edges_to, done_node.edges_cost):
+            new_edge = Neo_Node(edge)
+            new_edge.cost = done_node.cost + cost
+            #x,y が同じnodeがsearchedに入ってたら入れない
+            canInsert = True
+            for node in searched_nodes:
+                if node.x == edge.x and node.y == edge.y:
+                    canInsert = False
+            #x,yが同じnodeがunsearchedに入ってたらcostを比較する
+            for node in unsearched_nodes:
+                if node.x == edge.x and node.y == edge.y and new_edge.cost < node.cost:
+                    unsearched_nodes.remove(node)
+            if canInsert and new_edge.floor == done_node.floor:
+                unsearched_nodes.append(new_edge)
+    #goal_nodeと同じヤツを出力
+    for searched_node in searched_nodes:
+        if searched_node.x == goal_node.x and searched_node.y == goal_node.y:
+            result_time += searched_node.cost
+    return result_time * multiple_value(shop1.floor)
+#ノードの階数、x座標、y座標を記録
+    #nosが廊下にある分岐点、elsがエレベーターノード
+    nos201 = Node(2,253,273)
+#Shopの店名、カテゴリ、階数、x座標、y座標、リンクを持つノードを記録,本当は他にもショップの定義があります。
+	shop2 = Shop(2, " URBAN RESEARCH DOORS", "レディス・メンズ・キッズ・雑貨",4,263,235,nos403)
+# 配列読み込み
+    granfront = np.load("a.npy")
+     user = [(shop28,1),(shop70,2),(shop71,2),(shop72,2),(shop83,2),(shop86,2),(shop99,1),(shop123,2),(shop133,2),(shop144,2)]
+    limit_time = 7200
+    tb = 180 # 1
+    tw = 600 # 2
+    for i in range(len(user)):
+        shop_combinations = list(itertools.combinations(user, len(user)-i))
+        for shop_comb in shop_combinations:
+            shop_permutations = list(itertools.permutations(shop_comb))
+            result_time = 100000
+            result_root = []
+            for shop_perm in shop_permutations:
+                temp_time = 0
+                temp_shops = []
+                for sh, like in shop_perm:
+                    temp_shops.append(sh)
+                    if like == 1:
+                        temp_time += tb
+                    else:
+                        temp_time += tw
+                temp_time += compute_travel_time_between2shops(start_node, temp_shops[0])
+                previous_node = temp_shops[0]
+                for sh in temp_shops:
+                    if previous_node == sh:
+                        continue
+                    temp_time += granfront[sh.id][previous_node.id]
+                    previous_node = sh
+                if temp_time < result_time:
+                    result_time = temp_time
+                    result_root = temp_shops
+            # 時間がlimit_timeより少ないなら時間と順番書き込み
+            if result_time <= limit_time:
+                print("制限時間内にいける店舗の順番と時間：" + str(result_time))
+                with open("user1.csv", "a") as f:
+                    result = []
+                    result.append(result_time)
+                    for sh in result_root:
+                        result.append(sh.name)
+                    writer = csv.writer(f, lineterminator='\n')
+                    writer.writerow(result)
+```

追記

2017/03/05 11:13

投稿

okazujet

スコア11

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -7,6 +7,16 @@
 参考URL
 http://blog.livedoor.jp/komq/archives/1012592617.html
+要は2地点間の移動時間がすべて計算されている上での
+遺伝的アルゴリズムを用いた巡回セールスマン問題を解ける方法を知りたいですが、
+以下長文でやりたいことを書きます。

不必要な情報の削除

2017/03/05 08:36

投稿

okazujet

スコア11

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -42,42 +42,28 @@
 1と2でその地点に滞在する時間を変えており、それぞれtb = 180,tw = 600のように設定できるようにしています。
-・訪問する制限時間をT=7200のように設定しており、その時間内で滞在時間と移動時間を含めて
+・訪問する制限時間をT=7200のように設定しており、その時間内で滞在時間と移動時間を含めて移動パターンを作成します。
+・アンケート結果で1,2と回答しているお店のどこかに行くものとします。
+回答数が１０店舗であれば10C10+10C9+10C8+・・・・+10C1だけ巡回セールスマンを解いて
+かかった時間と順路を１行目からExcelファイルに吐き出せるようにしたいです。
+現在巡回セールスマン問題を総当たりで解いており
+１０店舗であれば２分ぐらいで修了するのですが、
+２０店舗になると何年もかかる計算になっており困っています。
+ご協力お願いします。
+不明瞭な点があれば質問をお願いします。
+###補足情報(言語/FW/ツール等のバージョンなど
-###発生している問題・エラーメッセージ
-```
-エラーメッセージ
-```
-###該当のソースコード
-```ここに言語を入力
-ここにご自身が実行したソースコードを書いてください
-```
-###試したこと
-課題に対してアプローチしたことを記載してください
-###補足情報(言語/FW/ツール等のバージョンなど)
-より詳細な情報
+python