Homework13 Finding the Cheapest Path查找最便宜路径_美国留学生作业assignment

Python海龟宝典含200多个原创的用turtle模块制作的创意程序,原名《Python趣味编程200例》。准备参加全国创意编程与智能设计大赛的同学们可以用来做参考。

本人已完成这份作业,需要答案,请联系本人,以下是作业部分内容。

python find cheapest path查找成本最低路径
python find cheapest path查找成本最低路径

Problem Setting

You are given a graph (𝑉,𝐸)(V,E), where each vertex 𝑥𝑉x∈V has a set of successors 𝑠(𝑥)s(x). There is one goal vertex 𝑔𝑉g∈V, that one must try to reach. The cost of visiting a vertex 𝑥𝑉x∈V is 𝑐(𝑥)>0c(x)>0.

The goal of the homework is to find, from every graph vertex 𝑥𝑉x∈V, the path to reach the goal 𝑔𝑉g∈V with minumum cost, and to compute for each vertex 𝑥𝑉x∈V its value 𝑣(𝑥)v∗(x), which corresponds to the minimum cost of reaching the goal.

You can compute 𝑣(𝑥)v∗(x) for every 𝑥𝑉x∈V via dynamic programming. First, you set:

𝑣(𝑥)={0+if 𝑥=𝑔;if 𝑥𝑔.(1)v(x)={0if x=g;+∞if x≠g.(1)

Basically, this encodes the fact that if you are at 𝑔g, you are at the goal, and you pay nothing. If you are not at 𝑔g, as we have not yet explored any path, the cost is infinite, as you don’t know how to go to 𝑔g (yet) .

Then, for every 𝑥𝑔x≠g, you update the cost 𝑣(𝑥)v(x) of 𝑥x via:

𝑣(𝑥):=𝑐(𝑥)+min𝑦𝑠(𝑥)𝑣(𝑦).(2)v(x):=c(x)+miny∈s(x)v(y).(2)

This because, to reach 𝑔g from 𝑥𝑔x≠g, one must first pay the price 𝑐(𝑥)c(x) of being at 𝑥x, and then one must go to a successor 𝑦y of 𝑔g. If the cost of then reaching 𝑔g from 𝑦y is 𝑣(𝑦)v(y), the total cost 𝑣(𝑥)v(x) from 𝑥x is 𝑐(𝑥)+𝑣(𝑦)c(x)+v(y). If 𝑥x has many successors, it is convenient to choose the successor with minimum cost: hence the minmin in the above equation.

So one way of solving the problem is this.

Initially, set 𝑣(𝑥)v(x) via (1). Then, repeat:

  • Update the value 𝑣(𝑥)v(x) at each 𝑥𝑔x≠g via (2)

Until nothing changes when the update is done.

The last part of the problem consists in finding a minimum-cost path to the goal. But this is easy to do: all you need to do is, when you update the costs 𝑣(𝑥)v(x) of a vertex via (2), you remember which successor 𝑦𝑠(𝑥)y∈s(x) gave you the minimum value (if there is more than one 𝑦𝑠(𝑥)y∈s(x) that gives you the minimum value, pick one of them at random). Call this the optimal successor 𝑏(𝑥)b(x) (for, “best at 𝑥x“) of 𝑥x:

𝑏(𝑥)=argmin𝑦𝑠(𝑥)𝑣(𝑦).(3)b(x)=arg⁡miny∈s(x)v(y).(3)

Then, to reach 𝑔g with minimum cost, you simply take the edge from 𝑥x to 𝑦1=𝑏(𝑥)y1=b(x), then to 𝑦2=𝑏(𝑦1)y2=b(y1), and so forth, until you reach 𝑔g. That is, you do not need to remember from each state its path to 𝑔g. You just need to remember the best successor of every state: following this chain of best successors will lead you to 𝑔g with minimum cost.

Here is the representation of a vertex, including its cost 𝑐()c(⋅), value 𝑣()v(⋅), and best successor 𝑏()b(⋅).

class Vertex(object):
    """This represents a vertex of the graph."""

    def __init__(self, cost, name=""):
        assert cost > 0
        assert len(name) > 0
        self.cost = cost
        self.name = name
        # This will be computed later
        self.value = None
        self.best_successor = None

    def __hash__(self):
        return hash(self.name)

    def __repr__(self):
        return "{}(c={},v={})".format(self.name, self.cost, self.value)

We define infinity, to implement (1). Yes, you can represent infinity in Python.

INFINITE = float("inf")

Question 1.

Here is our definition of the graph. In it, you need to complete the compute_values and best_path methods.

  • The compute_values method should perform the computation of the minimum cost for reaching the goal from each vertex, and should update x.value and x.best_successor for every vertex.
  • The best_path method should return the best path from a vertex to the goal, including both the initial vertex, and the goal vertex.
from collections import defaultdict

class Graph(object):

    def __init__(self):
        self.vertices = set()
        self.successors = defaultdict(set)
        self.goal = None # We will set this later. 

    def add_vertex(self, x, successors):
        """Adds a vertex x, with a specified set of successors."""
        # First, we want to make sure that both x and its successors are in the set
        # of graph vertices. 
        self.vertices.add(x)
        self.vertices.update(successors)
        # Then, we want to keep track of the successors of x. 
        self.successors[x] = successors

    def add_goal(self, x):
        """Adding a goal is similar to adding a vertex, except that the goal has 
        no successors (you have already arrived!). """
        self.goal = x
        self.add_vertex(x, set())

    def compute_values(self):
        """This function should compute the values x.value for each vertex 
        x of the graph, along with the best successor x.best_successor of each 
        vertex."""
        pass
        # This can be done in about a dozen lines of code.
        ### YOUR CODE HERE

    def best_path(self, x):
        """This function should output a list of vertices, starting at x, 
        and ending at the goal vertex, that consists of a minimum-cost path
        to the goal."""
        pass
        # This can be done in 5-6 lines of code. 
        ### YOUR CODE HERE

下面更多内容,在此不在列举..................
本站所有作品,教程等皆为原创,版权所有。只供个人及单位内部研究使用,对外展示或传播必需经本站同意,且注明来自本站。培训机构等用本站资源培训学生,需经本站授权。一旦付款,表示同意本站知识付费原则:数字商品,不支持退款。亦可直接向微信号scratch8付款购买。入住QQ群:225792826 和爱好者共同交流,并且能下载免费提供的Python资源(需提供真实姓名才可入群)
李兴球的博客_Python创意编程技术前沿_pygame » Homework13 Finding the Cheapest Path查找最便宜路径_美国留学生作业assignment

李兴球Python微信公众号文章列表

Python编程家长会花絮_萍乡中小学Python家长会现场

火星路上等着你_少儿从小学什么最好呢?

国家大力整顿教育培训机构,Scratch或Python少儿编程还有得教吗?

鸿蒙系统支持Python开发_可视化编程特别兴趣小组

Scratch作品转Python作品_小猴接桃

python海龟数据可视化。第七次全国人口普查历年数据图表

你的孩子Python编程学到哪个阶段了?给孩子报编程的家长,务必仔细一读。

五一神女来对话,看看她们聊什么?赠Python教案等。

五一快乐有大礼,告诉大家我是如何上Python课的。

Python名堂多,趣味到处有,劈开机械手,帧帧是图片。速算达人之猫狮大战正在进行。 逐字动画不独享,自动生成皆有它。2行代码自动生成字幕gif动画。 Python之潮来临,我在安源区教师科技创新能力的Python讲座

小心你的Python程序,它会是你的一面镜子。小方块闯迷宫.py源代码简析。送Scratch算法集。?

铃儿响钉铛_音效怎能忘_Python配音之Pygame混音器

人面桃花相映红_winsound模块简介

《Python昨晚我想你了》_开源的游戏海龟模块实例案例浅析

《八猫联动初体验》_来自游戏海龟模块的问候

喜爱春天的人儿啊 心地纯洁的人_Python逐行像素显示

旋转之三叶炫彩扇_蟒蛇与海龟的表演

彩虹欢迎字幕_三模合体滚图形

《Python海龟宝典》简介

100%错误的算法还在用,明明没有错别字,说我有11个错别字

奇怪的Python代码,谁能帮我解释一下??

人造地球系统让人类文明充满整个宇宙之Python32768版

深夜,是什么把你的大脑搞成一团浆糊!再谈少儿编程!

5线城市萍乡的少儿Python寒假班学的是什么内容?

关于纯少儿编程课程进化的自然选择

Python海龟画图经典作品_国庆中秋双重喜庆源代码免费下载

海龟为什么要自杀!turtle制作游戏秘籍之一

朋友,你是否知道我在仰望着你_Python神笔马良案例集

酷酷的爆炸效果_Python海龟画图不仅仅是画图

虫子满屏爬_三bug多线程示例程序浅析 少儿Python视频课程A级简介

给的gif图片加文字水印_拆帧与合帧(免费下载180个Python创意源码

用Python制作酷炫图形之如意金箍棒_颜色增加模块应用

简单的用Python做酷炫图形与动画

sb3转exe,sb3素材提取器,编程小子apk, 未公开的pygame游戏集/scratch/python少儿编程免费下载集合

夜幕下的霓虹

学本领,探索更大的世界!

李兴球博客 风火轮编程主页