无向图 [英] Undirected Graphs

问题描述

我有一个任务我试图用Java做的，但我很困惑如何设置/什么是下图中的节点。基本上，它是将笔式绘图仪问题，或更通常称为TSP问题。凡我下面输入为：

I have an assignment that I'm trying to do using Java, but I am confused about how to set up/what is the nodes for the following graph. Basically, it is the pen plotter problem, or more commonly known as the travelling salesman problem. Where my following input is:

Line between 4 1 and 4 4    
Line between 4 4 and 4 7    
Line between 2 6 and 4 4   
Line between 4 4 and 6 2  
Line between 6 6 and 4 4   
Line between 2 2 and 4 4   

和我的输出出来的：

<n> nodes explored
cost = 24.61
Move from 0 0 to 2 2
Draw from 2 2 to 4 4
Draw from 4 4 to 6 6
Move from 6 6 to 4 7
Draw from 4 7 to 4 4
Draw from 4 4 to 4 1
Move from 4 1 to 6 2
Draw from 6 2 to 4 4
Draw from 4 4 to 2 6

假设一张纸的左下角，将是您的开始（0,0），它会在坐标的每个坐标的一个节点，而我将如何确定何时移动和画线。我知道我应该用一个无向图，A *，但我仍然很困惑，哪些是节点（顶点），我怎么会决定​​什么时候移动，当画线，可能有人给我一些建议吗？

Assuming that the bottom left hand corner of the piece of paper, would be your start (0,0) and it goes up in coordinates, are each coordinate a node, and how would I determine when to move and draw a line. I know I should be using an undirected graph with A* but I'm still quite confused about which ones are nodes (vertices) and how I'd determine when to move and when to draw lines, could someone give me some advice?

编辑：请注意，是指在整个搜索探索节点的金额/数量

note that the refers to the amount/number of nodes explored throughout the whole search.

推荐答案

要使用A *，你首先需要一个的受理的启发函数。 [说明它是什么附于这个答案的末尾。

To use A*, you will first need an admissible heuristic function. [explanation what it is is attached at the end of this answer].

问题作为一个曲线图，答：*
定义G =（V，E）为您的图形，使得：
V = {所有可能的图纸prefixes} [即所有可能的管理单元射击每一个可能的平局。请注意，你不应该持有该图在内存中，但在运行中创建它，用下一个（）这将在后面解释。 【注意事项，实际上，每个国家实际需要只存储（1）其中是当前笔（2）线，其中已绘制]
E = {从一个所有可能发生的变化'快照'到另一个}
还需要 W：E-＆GT; R [重功能】将简单： W（点1，点2）= euclidian_distance （点1，点2）

Problem as a Graph for A:*
define G=(V,E) as your graph, such that:
V={all possible drawings prefixes} [i.e. all possible 'snap-shots' of each possible draw]. note you shouldn't hold this graph in memory, but create it on the fly, with next() which will be explained later. [note that practically, for each state you actually need to store only (1)where is the pen currently (2)which lines where already drawn]
E={all possible changes from one 'snap shot' to another}
You also need w:E->R [a weight function] which will be simply: w(point1,point2)=euclidian_distance(point1,point2)

您也应该定义下一：V-＆GT; P（V）：下一个（V）= {所有抓拍你可以从五，使用完全相同的一招/画
最后，你也应该定义 F ：所有的结束状态。 F = {所有的$ P $，所有的画线pfixes}

You should also define next:V->P(V): next(v)={all snap shots you can get from v, using exactly one move/draw
Finally, you should also define F: all "ending" states. F={all the prefixes which all the lines are drawn}

如何运行*： 出租车从快照的地方开始你的笔是（0,0），并没有画线[这是初始状态]，和继续下去，直到找到最后的国家之一。当你做，如果你的启发是有效的，你保证已经得到了最优化的解决方案，因为A *是的受理，并优化

How to run A*:
start from the snapshot where your pen is at (0,0), and no lines are drawn [this is the initial state], and keep going until you find one of the final states. when you do, if your heuristic is valid, you are guaranteed to have got the optimized solution, because A* is admissible and optimized

（*）的受理的启发函数：
让 H *（V）=实际距离目标从顶点v。
启发式函数h：V-> R是容许的，如果 H（V）＆LT; = H *（V）的V中各V

(*) admissible heuristic function:
let h*(v)=real distance to target from vertex v.
a heuristic function h:V->R is admissible if h(v)<=h*(v) for each v in V

您真正的挑战
为TSP最难的是找到一个可容许 ^ h 。它是如此困难，因为你不知道什么是最短的路径是，如果启发式功能不容许的，但不能保证找到的解决方案将得到优化。

Your real Challenge
The hard part for TSP is finding a an admissible h. It is so hard because you have no idea what's the shortest path is, and if the heuristic function is not admissible, it is not guaranteed that the solution found will be optimized.

建议：
您可能需要使用一些任何时间算法，当我做了类似的措施， [有多个代理解决TSP]我也用A *，而是开始与一个非有效的启发，并反复下跌，所以如果我有足够的时间，我找到了最佳的解决方案，如果没有 - 我回来，我能找到的最好的解决办法

Suggestion:
You might want to use some any time algorithm, When I did something similar to this, [solved TSP with multiple agents] I also used A*, but started with a non valid heuristic, and iteratively decreased it, so if I had enough time, I found optimal solution, and if not - I returned the best solution I could find.

这篇关于无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！