Python 中的加权随机图遍历

Question

基本上，我有一个 300 x 250 的区域，我想随机移动它。但是，在点 18750 和 9300 处有一些值得关注的区域（您可以通过执行以下操作计算出 x,y y = 0 while(num > x): num = num - x y += 1 你会得到坐标）。无论如何，如果起点是 (0,0)，我希望能够在该区域中随机移动，但在给定的两个点的一般区域中移动。也许一个人有更强的拉力，所以即使节点遍历导致更弱的节点，如果有足够的时间，它也会最终到达拉力更强的节点。

到目前为止，我已经有了这个来创建我的图形并创建我的顶点和边。它给了我一个 300x250 space，每个节点垂直和水平连接。 `

from igraph import *
g = Graph()
x = 300
y = 250
g.add_vertices(x*y)
li = []

for i in range(x-1):
    for j in range(y):
        li.append((i+j*x, i+1+j*x))
for i in range(x):
    for j in range(y-1):
        li.append((i+j*x, i+x+j*x))

g.add_edges(li)

gravity_points = [18750, 9300]
final_point = 24900

` 我该怎么做？我想让行进节点必须在每个静止节点上做出选择，但它在任何方向上行进的概率完全取决于重力点的权重。所以它可能有 10% 的机会向左走，有 10% 的机会向右走，有 50% 的机会向下走，有 30% 的机会向上走。像那样的东西。概率不必随着接近度而改变，而是随着重力点所在的方向而改变。

欢迎任何帮助！！提前谢谢你。

Answer 1

不确定，但也许您的问题不是找到算法，而是如何在这种情况下使用 igraph。这很棘手，因为它似乎没有为此要求添加任何内容。我将从描述算法开始：希望这能帮助您解决问题，直到我们得到答案。

随机遍历看起来像这样，在伪代码中：

traveller_node = start_node  # Chosen somehow

while not stopping_condition(traveller_node):
    possible_successors = traveller_node.successors()
    traveller_node = random_choice_from(possible_successors)

在这种情况下，最简单的方法是通过其 x,y 坐标来表示每个节点，包括旅行者节点。后继函数不需要依赖于图形，因为通常有四个选项，矩形的边缘除外。那么我们就可以直接编写您的问题：

traveller_x,traveller_y = 10,10  # Or whatever you want

while not at_gravity_points(traveller_x,traveller_y):
    directions = ["left","right","up","down"]
    if traveller_x == 0:
        directions.remove("left")
    if traveller_x == x:
        directions.remove("right")
    if traveller_y == 0:
        directions.remove("down")
    if traveller_y == y:
        directions.remove("up")

    to_gravity_point_1 = []
    if traveller_x < gravity_point_1_x:
        to_gravity_point_1.append("right")
    elif traveller_x > gravity_point_1_x:
        to_gravity_point_1.append("left")
    if traveller_y < gravity_point_1_y:
        to_gravity_point_1.append("up")
    elif traveller_y > gravity_point_1_y:
        to_gravity_point_1.append("down")

    # ... do the same to construct to_gravity_point_2
    # then use these two lists to construct your weighting scheme
    # then use random.random() to choose a direction from directions
    # according to that weighting.

    if direction == "left":
        traveller_x -= 1
    elif direction == "right":
        traveller_x += 1
    elif direction == "up":
        traveller_y += 1
    elif direction == "down":
        traveller_y -= 1

这一切都非常简单，我真的认为这不是您要问的。那么，也许您的问题是如何使用 igraph 的功能来做到这一点？在这种情况下，我的首选答案是 "why?"

但是，为了努力，你可以做这样的事情。首先用权重增加你的图表。通过迭代所有顶点来完成此操作，并且对于每个顶点，将它们的 x 和 y 与重力点的 x 和 y 进行比较。使用这些比较为它们的出边构建权重，并使用 igraph 中的加权图功能存储它们。

然后定义旅行者节点为igraph.Vertex。

然后重复：

对该顶点使用 igraph 后继函数来查找可能的后继。使用 igraph 权重查找来查找权重。使用 random.random() 根据权重在它们之间进行选择。将旅行者节点更改为选定的后继者。

在算法方面，这里唯一的区别是我们预先计算权重而不是按需计算。

Python 中的加权随机图遍历

Weighted Random Graph Traversal in Python

python

random

traversal

graph

weighted