Python 10万の惑星を100次元ほどの航法があった時の経路探索

人が100次元の航法を発見した時に役立つのではないだろうかというプログラム

惑星数を10万としてみました

 

空間的には整合性はとれていないはずです

 

0から99999の惑星までの経路を出してみました

テキスト版

 

#100次元を作ってみる 3次元をセルから前後左右上下1の6個とする
import random
class Cell:
    def make_path(self,i):
        self.path=random_n([i],dim_count*2)
def random_n(used,n):
    while len(used)!=n+1:
        r=random.randint(0,cell_count-1)
        if r not in used:
            used+=[r]
    return used[1:]
def find_path(s,e):
    sp=[(s,[s])]
    out=[s]
    while True:
        p,path=sp.pop(0)
        if e in cells[p].path:return path+[e]
        for np in cells[p].path:
            if np not in out:
                sp+=[(np,path+[np])]
                out+=[np]
    return []     
cell_count=100000
dim_count=100
cells=[]
for i in range(cell_count):
    cells+=[Cell()]
    cells[i].make_path(i)
print(find_path(0,cell_count-1))