程序员经验分享-hwhale

访问图中重复访问次数最少的所有节点

2023-12-28

我有一个基于图块的地图，其中几个图块是墙壁，其他图块是可步行的。可步行的瓷砖构成了我想在路径规划中使用的图表。我的问题是他们有什么好的算法可以找到访问图中每个节点的路径，从而最大限度地减少重复访问吗？

例如：

地图示例http://img220.imageshack.us/img220/3488/mapq.png http://img220.imageshack.us/img220/3488/mapq.png

如果底部黄色图块是起点，则以最少重复次数访问所有图块的最佳路径是：

路径示例http://img222.imageshack.us/img222/7773/mapd.png http://img222.imageshack.us/img222/7773/mapd.png

这条路径有两次重复访问。更糟糕的路径是在第一个路口左转，然后在三个已经访问过的方块上原路返回。

我不关心结束节点，但开始节点很重要。

Thanks.

Edit:

我在问题中添加了图片，但在查看时看不到它们。他们来了：

http://img220.imageshack.us/img220/3488/mapq.png http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png http://img222.imageshack.us/img222/7773/mapd.png

此外，在图表中我需要这个，因为永远不会出现最小重复次数 = 0 的情况。也就是说，要踏上地图中的每个图块，玩家必须至少穿过自己的路径一次。


你的措辞很糟糕——它可以简化为 NP 完全问题。如果你可以最大限度地减少重复访问，那么你可以将它们推到 0，然后你就会有一个哈密​​顿循环 http://mathworld.wolfram.com/HamiltonianCycle.html。这是solvable http://www.springerlink.com/content/6wkbcnbfvrnq86ev/，但是很难。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Search

graphtheory

Pathfinding

访问图中重复访问次数最少的所有节点 的相关文章

  • Java 中搜索和排序算法的高效实现

    有没有人有关于常见搜索和排序算法的一组 Java 代码实现的良好参考 剥猫皮的方法有很多种 很容易在网上找到各种算法的 Java 代码 但是 Java 中是否有实现这些不同算法的最有效方法的列表 例如有http www algorithmi

  • Prolog 同构图

    这里尝试解决同构图问题 作业信息 判断2个无向图是否同构 没有孤立的顶点 顶点数小于30 图的边作为谓词给出 即 e 1 2 f 1 2 我正在尝试使用以下方法 对于每对边 即图 1 和图 2 中的每条边 Try to bind the v

  • Google 自定义搜索引擎未给出预期的搜索结果

    我一直在尝试创建一个新的谷歌自定义搜索引擎 但是当我尝试一些查询时 搜索引擎没有给我预期的搜索 结果 在某些查询上它工作正常 但在其他查询上 它说 没有结果 我尝试添加我想要搜索的网站的 URL 但是当我尝试搜索该页面的关键字时 某些页面和

  • 为什么使用 Dijkstra 算法而不是最佳（最便宜）优先搜索？

    从我到目前为止所读到的来看 这最佳优先搜索 https en wikipedia org wiki Best first search在找到到达目标的最短路径方面似乎更快 因为 Dijkstra 算法在遍历图时必须放松所有节点 是什么让 D

  • 用于搜索内部文件的 ssh 命令

    几周前 我的两个网站可能被 ftp 暴力攻击所利用 破坏了我网站的许多文件 我发现他们通常会在js或php文件中插入以下代码 Trojan code removed as irrelevant to this question 我想通过 s

  • 从 WordPress 搜索结果页面获取类别名称

    在特定博客类别中进行搜索查询 重定向到 WP BLOG 主页面 后 我的搜索 URL 如下所示 online shop s category new posts category post type post 不幸的是 我无法在搜索结果页面

  • Node2vec 的工作原理

    我一直在读关于node2vec https cs stanford edu jure pubs node2vec kdd16 pdf嵌入算法 我有点困惑它是如何工作的 作为参考 node2vec 由 p 和 q 参数化 并通过模拟来自节点的

  • Unity InputField OnValueChanged事件显示InputField.text少一个字符

    我有一个InputField我用它作为搜索栏 我无法自动搜索OnValueChanged因为最初 文本字段将是 现在如果我输入任何字符a the inputField text还是 代替a因此 在添加下一个字符之前不会进行搜索 有没有办法在

  • 从中间部分匹配完成建议elasticsearch

    我有一个名为搜索建议具有以下 search suggest type completion analyzer simple payloads true preserve separators false preserve position

  • 删除networkx有向图中入度和出度等于1的所有节点

    假设我在 NetworkX 中制作了一个有向图 import networkx as nx G nx DiGraph n A B C D E F H I J K L X Y Z e A Z Z B B Y Y C C G G H G I I

  • 实时搜索错误

    我正在获取用户偏好和角色 一切正常并且数据接收正确 默认值放置在单选按钮上以突出显示用户当前拥有的选项 我正在使用 Antd Design Table 组件 问题 当我将用户首选项更改为打印文档时 它确实通过数据库的状态成功更改了它 但是现

  • H2数据库排序规则：选择什么？

    经过大量阅读和实验后 似乎我想要主要的搜索强度 但第三或相同的排序强度 主要问题 用 H2 或任何其他数据库 可以实现吗 第二个问题 我是这里唯一的人吗 或者你们中有人也喜欢上述组合吗 一些确认会对我的理智有所帮助 背景 看来排序规则只能在

  • 如何使用 Ansible when 条件在文件中搜索字符串

    我有一个变量中用 n 分隔的搜索字符串列表listofips 我想在文件中搜索该字符串hello csv在我的下面playbook dir 我可能遇到一些语法问题 我不确定 但下面是我尝试过的 set fact listofips 10 0

  • 将非方邻接矩阵导入 Networkx python

    我在下面有一些 pandas 数据框形式的数据 其中列代表离散技能 行代表离散工作 仅当工作需要该技能时才存在 1 否则为 0 skill 1 skill 2 job 1 1 0 job 2 0 0 job 3 1 1 我想使用 netwo

  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he

  • C 中的三元搜索

    我想在 C 中对整数进行三元搜索 我已经尝试过 但它对于特定情况效果不佳 请帮我删除以下程序中的错误 我的尝试 include

  • 实现快速 Javascript 搜索？

    基本上 我有一个带有文本框的页面和 ul 列在其下面 这 ul 由用户的朋友列表填充 用户开始在文本框中输入朋友的名字 例如按 r 我想立即更新 ul 每次按键仅显示名字以 R 开头的朋友 例如 Richard Redmond Raheem

  • 如何检查是否存在可能的路径？

    我正在开发一个基于 javascript 的实验性游戏 玩家必须在二维平铺地图上移动才能退出 请随意检查这个小提琴并演奏 http jsfiddle net moonlife 74vLd 我只是随机放置障碍物 但有时障碍物会挡住玩家和出口之

  • 以编程方式在 App Store 上运行搜索？

    是否可以从我的应用程序中打开 App Store 应用程序并运行搜索 我想看看是否有一个 appstore 类型的 URL 可以使用 就像 mailto 和 sms 分别打开邮件和短信一样 有谁知道这是否可能 编辑 更多信息 我一直在尝试使

  • 谷歌如何通过图像进行搜索？

    最近 谷歌推出了图片搜索的新功能 即通过图片搜索 我们可以通过在谷歌搜索框中上传图片来搜索其他图片 这怎么可能 http images google com http images google com Look at WP 基于内容的图像

随机推荐

  • 将字典保存到文件（numpy 和 Python 2/3 友好）

    我想在Python中进行分层键值存储 这基本上可以归结为将字典存储到文件中 我指的是任何类型的字典结构 可能包含其他字典 numpy 数组 可序列化的 Python 对象等等 不仅如此 我希望它能够存储经过空间优化的 numpy 数组 并在

  • FileUpload - 如果文件名存在，则在名称末尾的括号之间连接一个数字

    我想将文件 一次一个 上传到文件夹 GetUniqueName函数 下面提到 将返回一个唯一的文件名 这是我用来执行此操作的代码 public static string GetUniqueName string fileName stri

  • Three.js：在普通桌面上保持 60 FPS 的上限是多少？

    我目前正在使用 Three js 开发一款游戏 我已经学习软件工程四年了 并在后端专业工作了两年 但除了一些简单的 Unity 实验之外 我几乎没有接触过图形 根据 renderstats js 我目前有大约 22 000 个顶点和大约 8

  • 右对齐数据表列中的单元格内容

    我想右对齐outputText值 即下面的fee TableAmount 并且我想保持该列的标题居中 我必须将什么参数传递给下面的outputText才能实现此目的

  • Web API 性能？

    我刚在想 The WebApi随着routing mechanism以这样的方式工作 它读取http verb GET POST 等 然后搜索匹配的方法名称 参数 例如 If it s GETURI 是api Customers 5 方法应

  • StringBuilder.Append 与 StringBuilder.AppendFormat

    我想知道 StringBuilder 的情况 并且有一个问题希望社区能够解释 让我们忘记代码的可读性 其中哪一个是faster为什么 StringBuilder Append StringBuilder sb new StringBuild

  • android 4.x 上的输入元素在聚焦时无法设置样式

    Update 有一个修复 webkit user modify read write plaintext only 原问题 我试图将其归结为一个简单的例子 我有一个像这样的简单输入元素

  • 使用 NSOpenGLLayer 从单独的线程中绘制

    我正在开发一个应用程序 它需要使用 OpenGL 进行绘制 刷新率至少等于显示器的刷新率 我需要在单独的线程中执行绘图 以便绘图永远不会被激烈的 UI 操作锁定 实际上我正在使用NSOpenGLView结合CVDisplayLink我可以毫

  • 未捕获的类型错误：无法读取未定义的属性“localStorage”

    我在backbonejs应用程序中有以下内容 MODEL var app app ledger Backbone Model extend COLLECTION app ledgerList Backbone Collection exte

  • 控件库的 WPF 样式

    我有一个图书馆 Styles DLL 其中包含带键的 WPF 集合Styles 我有一个班级图书馆 Module DLL 其中包含多个Windows and UserControls可以在各种应用程序之间共享 我用的是带键的Styles定义

  • Gensim：KeyError：“单词不在词汇表中”

    我有一个使用 Python 的 Gensim 库训练过的 Word2vec 模型 我有一个标记化列表 如下所示 词汇量为 34 但我只给出 34 中的几个 b let know buy someth featur mashabl might

  • 将不同长度的列表列表转换为numpy数组[重复]

    这个问题在这里已经有答案了 我有不同长度的列表列表 例如 1 2 3 4 5 6 7 8 9 并想将其转换为numpy整数数组 我理解 子 数组numpy多维数组的长度必须相同 那么 将上面示例中的列表转换为列表的最有效方法是什么 nump

  • 什么在实体中调用 setter？

    在实体框架中 您必须创建一个派生自的类DbContext具有 IDbSet 属性 实体框架中什么调用 setter 以及它是如何工作的 当您的自定义上下文类被实例化时 基类DbContext构造函数调用一个名为的私有方法Initialize

  • 为什么java hashCode()中经常使用XOR，而其他按位运算符却很少使用？

    我经常看到这样的代码 int hashCode return a b Why XOR 在所有位操作中 XOR 具有最好的位混洗属性 这个真值表解释了原因 A B AND 0 0 0 0 1 0 1 0 0 1 1 1 A B OR 0 0

  • Jackson - 结合 @JsonValue 和 @JsonSerialize

    我正在尝试组合 JsonValue and JsonSerialize 让我们从我当前的容器类开始 public class Container private final Map

  • javafx 移植应用程序性能不佳

    我刚刚使用 gradlew 将一个名为 PuzzlePieces 的示例 netbeans javafx 项目移植到 android 中 该应用程序的性能如此糟糕 是什么原因造成的 我的设备 LG E975 4 4 kitkat This

  • 无法转换类型的对象

    在我的 wpf 应用程序中尝试将字符串从一个窗口发送到另一个窗口时出现错误 无法将 WpfApplication4 LoginWindow 类型的对象强制转换为 WpfApplication4 MainWindow 类型 在我的登录窗口中

  • 如何在 jersey 2.0 中使用 hk2 注入常量？

    如何在球衣中使用 HK2 将常量注入某个类 有了Guice 我可以上一些像这样的课程 public class DependsOnFoo Inject public DependsOnFoo Named FOO String foo 我会在

  • python 中基于 websocket 的 MQTT

    python 是否支持通过端口 8080 订阅 mqtt 代理 import sys import paho mqtt client as mqtt def on connect mqttc obj flags rc print rc st

  • 访问图中重复访问次数最少的所有节点

    我有一个基于图块的地图 其中几个图块是墙壁 其他图块是可步行的 可步行的瓷砖构成了我想在路径规划中使用的图表 我的问题是他们有什么好的算法可以找到访问图中每个节点的路径 从而最大限度地减少重复访问吗 例如 地图示例http img220 i

热门标签