修改Dijkstra以找到给定额外属性的最优化最短路径 [英] Modified Dijkstra to find most optimized shortest path given extra properties
问题描述
这是针对我在
我想到的第一个版本的解决方案是在计算路径时累积总的连续断开时间，因此它不能超出阈值 T 。每当我们到达有连接的路由时（无论带宽是否更简单），我们都会重置累加。进一步考虑带宽，因为我们也有连接带宽的价值，我们可以从总的累计断开时间中扣除连接带宽的值（是否有效？！）
<一个重要的事情是考虑下面的例子。不超过总断开阈值不应该导致通过一条非常远的路线，从而增加总旅行时间！为此，我想到了这种一般方法：解决断线阈值问题，例如 T1，T2，... Tk ，计算最佳路径（或一组最佳路径路径可能？！），并计算每个对应的总行程时间。然后应用我们上面的目标函数，看看什么是最优解。我们可以进一步在两个样本之间找出解决方案，以使用类似二进制搜索的方法找到更优化的解决方案。
请有人可以帮我解决问题吗？显然，我的解决方案是不正确的，如果是这样，甚至不可能在多项式时间。也许近似算法？！任何有助于找到解决方案，高度赞赏。随意添加更多细节或假设，或修改问题。这个问题比我想象的要难。
解决方案首先找到完整答案，不可行。请参阅 http://phys.org/news/2015-05-maths- congestionsprings-traffic.html 的文章，概述您将遇到的一些实际复杂性和数值不稳定性。另外，还有一个示例，即增加道路可能会使整个网络变得更糟。然而，我们可以在实际中很好地解决您在寻找IP网络问题方面的问题。在。谷歌搜索给了我 https://www.cs.princeton.edu/~ jrex / papers / opthand04.pdf 作为从哪里开始学习文献的建议。
This is a follow-up question for a question I asked at here. The problem is mapped to a graph with say non-negative weights on edges (no preference if it can be directed or not). However, along with a weight which is actually distance, we also have another property which is data coverage of the edge which can be important factor which route to select given how severe I need internet on my phone (for real-time gaming for example I need good bandwidth). So overall, we want to somehow find a trade-off between the length of the path and network bandwidth to solve the problem of finding most optimized and shortest path between two cities. However, an important feature is that the algorithm should be dynamic. Once we arrived to a node, depending on our current state of need we might change the pre-determined path.
OK. For simplicity, let's say each edge is associated with two properties: A) a distance or travel time or whatever, as a regular weight, and B) network bandwidth as a secondary property to show how good network is.
For constraints and objective function, say we want to minimize the total distance (or travel time), but depending to our current state, we also want to minimize the total disconnection time or maximize the total sum of path bandwidths. Optionally, say we can not tolerate total continuous disconnection time of more than a threshold T. So this can be a constraint on the problem. The simplest of such objective functions can be f()=total time of travel + a*time of disconnection. The a co-efficient determines how important connectivity can be for us at each time.
To tackle the fact that edges can have partial disconnections, after a bit of think, I came into a solution that let's insert nodes in between. That makes the problem easier to solve. So basically each route either has disconnection, or connection with a bandwidth of specific value.
A first-version solution that came into my mind was to accumulate the total continuous disconnection times whenever we are computing a path, so it can not go beyond the threshold T. And whenever we reached a route with connection (regardless of bandwidth for a simpler problem), we just reset the accumulation. Further to account for bandwidth, since we also have value for connection bandwidth, we can just deduct the value of connection bandwidth from the total accumulated disconnection time (does it work?!)
One important thing is to consider the following example figure. Not exceeding the total disconnection threshold shouldn't lead to go through a very far route which increases the total time of travel! For that, I thought about this general approach: Solve the problem for disconnection threshold of say T1, T2, ...Tk, compute the best path (or a set of best paths maybe?!), and compute the corresponding total travel time for each. Then apply the objective function that we have above and see what is the most optimum solution. We can further pin point the solution between two samples to find more optimum solution using a binary-search-like approach.
Please, can someone please help me to solve the problem? Apparently my solution is not correct, and if it was, even not possible in polynomial time. Maybe approximation algorithms?! Any helps to find a solution is highly appreciated. Feel free to add more details or assumptions, or revise the problem. The problem is harder than what I thought.
First of all finding the perfect answer to this question for the whole network is computationally infeasible. See http://phys.org/news/2015-05-maths-congestionsprings-traffic.html for an article outlining some of the practical complexity and numerical instability that you'll encounter. As well as a demonstration that adding roads can make the whole network worse.
However we can solve it in practice reasonably well for exactly the IP networking problem that you're looking at. A google search gave me https://www.cs.princeton.edu/~jrex/papers/opthand04.pdf as a suggestion for where to start learning the literature.
这篇关于修改Dijkstra以找到给定额外属性的最优化最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
