图论为什么这么难_图论是什么，为什么要关心？
圖論為什么這么難
Graph theory might sound like an intimidating and abstract topic to you, so why should you even spend your time reading an article about it? However, although it might not sound very applicable, there are actually an abundance of useful and important applications of graph theory! In this article, I will try to explain briefly what some of these applications are. In doing so, I will do my best to convince you that having at least some basic knowledge of this topic can be useful in solving some interesting problems you might come across.
圖形理論對您來說聽起來像是一個令人生畏的抽象話題，那么為什么還要花時間閱讀有關它的文章？ 但是，盡管聽起來可能不太適用，但實際上圖論有很多有用而重要的應用！ 在本文中，我將嘗試簡要解釋其中的一些應用程序。 為此，我將盡力說服您，至少具有該主題的一些基本知識對于解決您可能遇到的一些有趣問題很有用。
In this article, I will through a concrete example show how a route planning/optimization task can be formulated and solved using graph theory. More specifically, I will consider a large warehouse consisting of 1000s of different items in various locations/pickup points. The challenge here is, given a list of items, which path should you follow through the warehouse to pickup all items, but at the same time minimize the total distance traveled? For those of you familiar with these kind of problems, this has quite some resemblance to the famous traveling salesman problem. (A well known problem in combinatorial optimization, important in theoretical computer science and operations research).
在本文中，我將通過一個具體示例展示如何使用圖論來制定和解決路線規(guī)劃/優(yōu)化任務。 更具體地說，我將考慮一個大型倉庫，該倉庫由位于不同位置/提貨點的數千種不同物品組成。 這里的挑戰(zhàn)是，給定一個物品清單，您應該沿著該路徑走入倉庫以拾取所有物品，但同時要使總行駛距離最小化？ 對于那些熟悉這類問題的人來說，這與著名的旅行推銷員問題非常相似。 ( 組合優(yōu)化中的一個眾所周知的問題，在理論計算機科學和運籌學中很重要)。
As you might have realized, the goal of this article is not to give a comprehensive introduction to graph theory (which would be quite a tremendous task). Through a real-world example, I will rather try to convince you that knowing at least some basics of graph theory can prove to be very useful!
您可能已經意識到，本文的目的不是全面介紹圖論(這將是一項艱巨的任務)。 通過一個真實的例子，我寧愿說服您，至少了解圖論的一些基礎知識會證明是非常有用的！
I will start with a brief historical introduction to the field of graph theory, and highlight the importance and the wide range of useful applications in many vastly different fields. Following this more general introduction, I will then shift focus to the warehouse optimization example discussed above.
我將首先對圖論領域進行簡要的歷史介紹，然后重點介紹在許多截然不同的領域中的重要性和廣泛的有用應用。 在進行了更一般的介紹之后，我將把重點轉移到上面討論的倉庫優(yōu)化示例。
圖論的歷史 (The history of Graph Theory)
The basic idea of graphs were first introduced in the 18th century by the Swiss mathematician Leonhard Euler, one of the most eminent mathematicians of the 18th century (and of all time, really). His work on the famous “Seven Bridges of K?nigsberg problem”, are commonly quoted as origin of graph theory.
圖的基本概念是由瑞士數學家萊昂哈德·歐拉 ( Leonhard Euler)于18世紀首次提出的， 萊昂哈德·歐拉 ( Leonhard Euler)是18世紀最杰出的數學家之一(實際上是有史以來)。 他關于著名的“ 柯尼斯堡七橋問題 ”的著作通常被認為是圖論的起源。
The city of K?nigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands — Kneiphof and Lomse — which were connected to each other, or to the two mainland portions of the city, by seven bridges (as illustrated in the below figure to the left). The problem was to devise a walk through the city that would cross each of those bridges once and only once.
普魯士的克尼格斯堡市(現為俄羅斯加里寧格勒)位于普雷格爾河的兩側，包括兩個大島，克奈普霍夫和隆塞，它們相互連接，或者與該市的兩個大陸部分相連，七個橋(如下圖左圖所示)。 問題是要設計一條穿過城市的步行路線，一次只能穿過一次這些橋梁。
Euler, recognizing that the relevant constraints were the four bodies of land & the seven bridges, drew out the first known visual representation of a modern graph. A modern graph, as seen in bottom-right image, is represented by a set of points, known as vertices or nodes, connected by a set of lines known as edges.
歐拉認識到相關的約束條件是四塊土地和七座橋梁，因此得出了現代圖形的第一個已知視覺表示。 一個現代的曲線圖，如在右下方圖像，是由一組點，公知的為v ertices或節(jié)點，由一組被稱為邊緣線的連接來表示。
Wikipedia維基百科This abstraction from a concrete problem concerning a city and bridges etc. to a graph makes the problem tractable mathematically, as this abstract representation includes only the information important for solving the problem. Euler actually proved that this specific problem has no solution. However, the difficulty he faced was the development of a suitable technique of analysis, and of subsequent tests that established this assertion with mathematical rigor. From there, the branch of math known as graph theory lay dormant for decades. In modern times, however, it’s applications are finally exploding.
從有關城市和橋梁等具體問題的抽象到圖表，使該問題在數學上易于處理，因為這種抽象表示僅包含解決問題的重要信息。 歐拉實際上證明了這個特定問題沒有解決方案。 但是，他面臨的困難是開發(fā)一種合適的分析技術以及隨后的測試，這些測試以嚴格的數學方法確立了這一主張。 從那里開始，數十年來一直處于Hibernate狀態(tài)的稱為圖論的數學分支。 然而，在現代，它的應用終于爆炸了。
圖論概論 (Introduction to Graph Theory)
As mentioned previously, I do not aim to give a comprehensive introduction to graph theory. The following section still contains some of the basics when it comes to different kind of graphs etc., which is of relevance to the example we will discuss later on path optimization.
如前所述，我并不打算對圖論進行全面介紹。 以下部分仍包含有關不同種類的圖等的一些基礎知識，這與我們稍后將討論路徑優(yōu)化的示例相關。
Graph Theory is ultimately the study of relationships. Given a set of nodes & connections, which can abstract anything from city layouts to computer data, graph theory provides a helpful tool to quantify & simplify the many moving parts of dynamic systems. Studying graphs through a framework provides answers to many arrangement, networking, optimization, matching and operational problems.
圖論最終是對關系的研究。 給定一組節(jié)點和連接，可以抽象化從城市布局到計算機數據的所有內容，圖論提供了一個有用的工具，可以量化和簡化動態(tài)系統(tǒng)的許多移動部分。 通過框架研究圖形可為許多布置，網絡，優(yōu)化，匹配和操作問題提供答案。
Graphs can be used to model many types of relations and processes in physical, biological, social and information systems, and has a wide range of useful applications such as e.g.
圖形可用于對物理，生物，社會和信息系統(tǒng)中的許多類型的關系和過程進行建模，并且具有廣泛的有用應用，例如
As mentioned, there are several types of graphs that describe different kind of problems (and the constraints within them). A nice walk-through of various types of graphs can also be found in a previous article by Kelvin Jose, and the below section represents a subset of that article.
如前所述，有幾種類型的圖描述了不同類型的問題(以及其中的約束)。 凱爾文·何塞 ( Kelvin Jose)的上一篇文章中也可以找到各種圖形的很好的演練，下面的部分代表該文章的子集。
圖的類型 (Types of Graphs)
There are different types of graph representations available and we have to make sure that we understand the kind of graph we are working with when programmatically solving a problem which includes graphs.
有不同類型的圖表示形式，當以編程方式解決包括圖的問題時，我們必須確保我們了解要使用的圖的類型。
Undirected Graphs
無向圖
As the name shows, there won’t be any specified directions between nodes. So an edge from node A to B would be identical to the edge from B to A.
顧名思義，節(jié)點之間不會有任何指定的方向。 因此，從節(jié)點A到B 的邊緣 將 與 從B到A的邊緣 相同 。
In the above graph, each node could represent different cities and the edges show the bidirectional roads.
在上圖中，每個節(jié)點可以代表不同的城市，邊緣顯示雙向道路。
Directed Graphs (DiGraphs)
有向圖(DiGraphs)
Unlike undirected graphs, directed graphs have orientation or direction among different nodes. That means if you have an edge from node A to B, you can move only from A to B.
與無向圖不同，有向圖 在不同節(jié)點之間 具有方向或 方向 。 這意味著，如果從節(jié)點A到B有一條邊，則只能從A移到B。
WIkiMediaWIkiMediaLike the previous example, if we consider nodes as cities, we have a direction from city 1 to 2. That means, you can drive from city 1 to 2 but not back to city 1, because there is no direction back to city 1 from 2. But if we closely examine the graph, we can see cities with bi-direction. For example cities 3 and 4 have directions to both sides.
像前面的示例一樣，如果我們將節(jié)點視為城市，則我們有一個從城市1到2的方向。這意味著，您可以從城市1到2行駛，但不能返回城市1，因為沒有從該方向返回城市1的方向。 2.但是，如果我們仔細檢查圖表，我們會看到雙向的城市。 例如，城市3和4向兩側都有方向。
Weighted Graphs
加權圖
Many graphs can have edges containing a weight associated to represent a real world implication such as cost, distance, quantity etc …
許多圖的邊緣可能包含權重，以表示真實世界的含義，例如成本，距離，數量等。
Credit: Estefania Cassingena Navone viafreecodecamp.org 圖片來源 ： Estefania Cassingena Navone通過freecodecamp.orgWeighted graphs could be either directed or undirected graph. The one we have in this example is an undirected weighted graph. The cost (or distance) from the green to the orange node (and vice versa) is 3. Like our previous example, if you want to travel between two cities, say city green and orange, we would have to drive 3 miles. These metrics are self-defined and could be changed according to the situations. For a more elaborated example, consider you have to travel to city pink from green. If you look at the city graph, we can’t find any direct roads or edges between the two cities. So what we can do is to travel via another city. The most promising routes would be starting from green to pink via orange and blue. If the weights are costs between cities, we would have to spend 11$ to travel via blue to reach pink but if we take the other route via orange, we would only have to pay 10$ for the trip.
加權圖 可以是有向圖或無向圖。 在此示例中，我們得到的是無向加權圖。 從綠色節(jié)點到橙色節(jié)點(反之亦然)的成本(或距離)為3。像我們前面的示例一樣，如果您要在兩個城市之間旅行，例如綠色和橙色，則必須行駛3英里。 這些指標是自定義的，可以根據情況進行更改。 對于更詳細的示例，請考慮您必須從綠色到粉紅色的城市。 如果您查看城市圖，我們在兩個城市之間找不到任何直接的道路或邊緣。 因此，我們可以做的是穿越另一個城市。 最有希望的路線將是從綠色到粉紅色，再到橙色和藍色。 如果權重是城市之間的成本，那么我們將不得不花費11美元通過藍色旅行到達粉紅色，但是如果我們通過橙色乘坐另一條路線，那么我們只需為這次旅行支付10美元。
There may be several weights associated with each edge, including distance, travel time, or monetary cost. Such weighted graphs are commonly used to program GPS’s, and travel-planning search engines that compare flight times and costs.
每個邊緣可能有多個權重，包括距離，行駛時間或金錢成本。 這樣的加權圖通常用于對GPS進行編程，并比較旅行時間和費用的旅行計劃搜索引擎。
圖論→路線優(yōu)化 (Graph Theory → Route optimization)
Having (hopefully) convinced you that graph theory is worth knowing something about, it is now time to focus on our example case of route planning when picking items in our warehouse.
(希望)使您相信圖論值得一讀，現在是時候在我們的倉庫中揀選項目時關注路線規(guī)劃的示例案例。
挑戰(zhàn)： (Challenge:)
The challenge here is that given a “picking list” as input, we should find the shortest route that passes all the pickup points, but also complies to the restrictions with regard to where it is possible/allowed to drive. The assumptions and constraints here are that crossing between corridors in the warehouse is only allowed at marked “turning points”. Also, the direction of travel must follow the specified legal driving direction for each corridor.
這里的挑戰(zhàn)是，在輸入“揀選清單”的情況下，我們應該找到經過所有揀選點的最短路線，而且還要遵守關于可能/允許行駛的地點的限制。 這里的假設和約束條件是，僅允許在標記的“轉折點”處穿越倉庫的走廊。 另外，每個走廊的行駛方向必須遵循指定的合法行駛方向。
解： (Solution:)
This problem can be formulated as an optimization problem in graph theory. All pickup points in the warehouse form a “node” in the graph, where the edges represent permitted lanes/corridors and distances between the nodes. To introduce the problem more formally, let us start from a simplified example.
這個問題可以用圖論的形式表達為優(yōu)化問題。 倉庫中的所有取貨點都在圖中形成一個“節(jié)點”，其邊緣表示允許的車道/走廊以及節(jié)點之間的距離。 為了更正式地介紹這個問題，讓我們從一個簡化的例子開始。
The graph below represents 2 corridors with 5 shelves/pickup-points per corridor. All shelves are here represented as a node in the graph, with an address ranging from 1–10. The arrows indicate the permitted driving direction, where the double arrows indicate that you can drive either way. Simple enough, right?
下圖顯示了2條走廊，每個走廊有5個擱板/拾取點。 在此，所有架子都表示為圖中的節(jié)點，地址范圍為1-10。 箭頭指示允許的行駛方向，雙箭頭指示您可以兩種方式行駛。 很簡單，對不對？
Being able to represent the permitted driving routes in the form of a graph, means that we can use mathematical techniques known from graph theory to find the optimal “driving route” between the nodes (i.e., the stock shelves in our warehouse).
能夠以圖形的形式表示允許的行駛路線，這意味著我們可以使用圖形理論中已知的數學技術來找到節(jié)點(即，我們倉庫中的貨架)之間的最佳“行駛路線”。
The example graph above can be described mathematically through an ?adjacency matrix?. The adjacency matrix to the right in the below figure is thus a representation of our ?warehouse graph?, which indicates all permitted driving routes between the various nodes.
上面的示例圖可以通過《 鄰接矩陣 》進行數學描述。 因此，下圖右側的鄰接矩陣是我們“倉庫圖”的表示，該圖表示各個節(jié)點之間所有允許的行駛路線。
Example 1: You are allowed to travel from node 2 → 3, but not from 3 → 2. This is indicated by the “1” in the adjacency matrix to the right.
示例1：允許您從節(jié)點2→3出發(fā)，但不能從3→2出發(fā)。這由右側鄰接矩陣中的“ 1”指示。
Example 2: You are allowed to go from both node 8 → 3, and from 3 → 8, again indicated by the “1”`s in the adjacency matrix (which in this case is symmetric when it comes to travel direction).
示例2：允許您從節(jié)點8→3和3→8出發(fā)，再次由鄰接矩陣中的“ 1”表示(在這種情況下，關于行駛方向是對稱的)。
回到我們的倉庫問題： (Back to our warehouse problem:)
A real warehouse is of course bigger and more complex than the above example. However, the main principles of how to represent the problem through a graph remains the same. To make the real problem slightly simpler (and more visually suitable for this article), I have reduced the total number of shelves/pickup-points (approximately every 50th shelf included, marked with black squares in the below figure). All pickup points are given an address (“node number”) from 1–74. The other relevant constraints mentioned earlier, such as permitted driving directions in each of the corridors, as well as the allowed “turning points” and shortcuts between the corridors are also indicated in the figure..
實際的倉庫當然比上面的示例更大，更復雜。 但是，如何通過圖形表示問題的主要原理保持不變。 為了使實際問題更簡單(并且更直觀地適合本文)，我減少了架子/拾取點的總數(大約每50個架子中有一個，在下圖中用黑色正方形標記)。 將為所有拾取點分配一個1到74之間的地址(“節(jié)點號”)。 圖中還標出了前面提到的其他相關約束，例如每個走廊中的允許行駛方向以及走廊之間的允許“轉彎點”和捷徑。
Graph representation of our simplified warehouse我們簡化倉庫的圖形表示The next step is then to represent this graph in the form of a adjacency matrix. Since we are here interested in finding both the optimal route and total distance, we must also include the driving distance between the various nodes in the matrix.
然后，下一步就是以鄰接矩陣的形式表示該圖。 由于我們對尋找最佳路線和總距離感興趣，因此我們還必須在矩陣中包括各個節(jié)點之間的行駛距離。
Adjacency matrix for the “warehouse graph”“倉庫圖”的鄰接矩陣This matrix indicates all constraints with regard to both the permitted direction of travel, which “shortcuts” are permitted, any other restrictions as well as the driving distance between the nodes (illustrated through the color). As an example, the “shortcut” between nodes 21 and 41 shown in the graph representation can clearly be identified also in the adjacency matrix. The “white areas” of the matrix represents the paths that are not allowed, indicated through an “infinite” distance between those nodes.
該矩陣指示關于允許的行進方向(允許使用“快捷方式”)，所有其他限制以及節(jié)點之間的行駛距離(通過顏色顯示)的所有限制。 作為示例，在圖形表示中所示的節(jié)點21和41之間的“快捷方式”也可以在鄰接矩陣中清楚地識別。 矩陣的“白色區(qū)域”表示不允許的路徑，通過這些節(jié)點之間的“無限”距離表示。
從圖表示到路徑優(yōu)化 (From graph representation to path optimization)
Just having an abstracted representation of our warehouse in the form of a graph, does of course not solve our actual problem. The idea is rather that through this graph representation, we can now use the mathematical framework and algorithms from graph theory to solve it!
僅僅以圖表的形式對我們的倉庫進行抽象表示，當然并不能解決我們的實際問題。 想法是通過這種圖形表示，我們現在可以使用圖形理論中的數學框架和算法來解決它！
Since graph optimization is a well-known field in mathematics, there are several methods and algorithms that can solve this type of problem. In this example case, I have based the solution on the “Floyd-Warshall algorithm”, which is a well known algorithm for finding shortest paths in a weighted graph. A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of nodes. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.
由于圖優(yōu)化是數學領域的眾所周知的領域，因此有幾種方法和算法可以解決此類問題。 在此示例情況下，我基于“ Floyd-Warshall算法 ”解決方案，這是一種用于在加權圖中找到最短路徑的眾所周知的算法 。 算法的一次執(zhí)行將找到所有節(jié)點對之間最短路徑的長度(總權重)。 盡管它不返回路徑本身的詳細信息，但可以通過對算法的簡單修改來重建路徑。
If you give this algorithm as input a “picking order list” where you go through a list of items you want to pick, you should then be able to obtain the optimal route which minimize the total driving distance to collect all items on the list.
如果您將此算法作為輸入輸入“領料單列表”，然后在該列表中瀏覽要領料的物品列表，則應該能夠獲得最佳路線，該路線將使總行駛距離最小化以收集清單上的所有物品。
Example: Let us start by visualizing the results for a (short) picking list as follows: Start from node ?0?, pick up items at location/node 15, 45, 58 and 73 (where these locations are illustrated in the figure below). The algorithm finds the shortest allowable route between these points through calculating the “distance matrix”, D, which can then be used to determine the total driving distance between all locations/nodes in the picking list.
示例：讓我們首先以可視化方式顯示一個(簡短的)揀貨清單，如下所示：從節(jié)點?0?開始，在位置/節(jié)點15、45、58和73處揀貨(這些位置如下圖所示) )。 該算法通過計算“距離矩陣” D找到這些點之間的最短允許路線，然后將其用于確定領料單中所有位置/節(jié)點之間的總行駛距離。
Step 1: D[0][15] → 90 m
步驟1： D [0] [15]→90 m
Step 2: D[15][45] →52 m
步驟2： D [15] [45]→52 m
Step 3: D[45][58] → 34 m
步驟3： D [45] [58]→34 m
Step 4: D[58][73] → 92 m
步驟4： D [58] [73]→92 m
Total distance = 268m
總距離= 268m
Optimized driving route from picking list從揀貨清單優(yōu)化駕駛路線Have tested several “picking lists” as input and verifying the proposed driving routes and calculated distance, the algorithm has been able to find the optimal route in all cases. The algorithm respects all the imposed constraints, such as the permitted direction of travel, and uses all permitted “shortcuts” to minimize the total distance.
測試了多個“揀選清單”作為輸入，并驗證了建議的行駛路線和計算出的距離，該算法已能夠在所有情況下找到最佳路線。 該算法遵守所有強加的約束條件，例如允許的行進方向，并使用所有允許的“快捷方式”來最小化總距離。
從路徑優(yōu)化到有用的見解 (From path optimization to useful insights)
As shown through the above example, we have developed an optimization algorithm that calculates the optimal driving route via all points on a picking order list (for a simplified version of the warehouse). By providing a list of picking orders as input, one can thus relatively easily calculate statistics on typical mileage per. picking order. These statistics can then also be filtered on various information such as item type, customer, date, etc. In the following section, I have thus picked a few examples on how one can extract interesting statistics from such a path optimization tool.
如上面的示例所示，我們開發(fā)了一種優(yōu)化算法，該算法可通過揀貨訂單列表上的所有點(針對倉庫的簡化版本)計算最佳行駛路線。 通過提供一列提貨單作為輸入，因此可以相對輕松地計算出每人平均行駛里程的統(tǒng)計數據。 領料單。 然后，還可以根據各種信息(例如項目類型，客戶，日期等)過濾這些統(tǒng)計信息。因此，在以下部分中，我選擇了一些示例，說明如何從這種路徑優(yōu)化工具中提取有趣的統(tǒng)計信息。
In doing this, I first generated 10.000 picking order lists where the number of items per list ranges from 1–30 items, located at random pickup points in the warehouse (address 3–74 in the figure above). By performing the path optimization procedure over all these picking list, we can then extract some interesting statistics.
為此，我首先生成了10.000個揀貨訂單清單，其中每個清單的物品數量在1至30件之間，位于倉庫中的隨機取貨點(上圖中的地址3–74)。 通過對所有這些選擇列表執(zhí)行路徑優(yōu)化過程，我們可以提取一些有趣的統(tǒng)計信息。
Example 1: Calculate mileage as a function of the number of units per. picking order list. Here, you would naturally assume that the total mileage increases the more items you have to pick. But, at some level, this will start to flatten out. This is due to the fact that one eventually has to stop by all the corridors in the warehouse to pick up goods, which then prevents us from making use of clever “shortcuts” to minimize the total driving distance. This tendency can be illustrated in the figure below to the left, which illustrates that for more than approximately 15–20 units per picking order, adding extra items does not make the total mileage much longer (as you have to drive through all corridors of the warehouse anyway). Note that the figures show a “density plot” of the distribution of typical mileage per. picking orders list
示例1：根據每單位數量計算里程。 領料單清單。 在這里，您自然會假設總里程數增加了您必須選擇的項目。 但是，在某種程度上，這將開始趨于平緩。 這是由于這樣一個事實，即最終必須在倉庫的所有走廊停下來取貨，這又使我們無法利用巧妙的“捷徑”來最小化總行駛距離。 這種趨勢可以在左下圖中說明，該圖說明，對于每個揀配訂單，大約15-20個單位以上，添加額外的物品并不會使總行駛里程更長(因為您必須開車穿過貨車的所有走廊)倉庫)。 注意，這些圖顯示了每英里典型行駛里程分布的“密度圖”。 領料單清單
Another interesting statistic, which shows the same trend, is the distribution of driving distance per picked item in the figure to the right. Here, we see that for picking lists with few items, the typical mileage per. item is relatively high (with a large variance, depending on how “l(fā)ucky” we are with some items being located in the same corridor etc.). For picking lists with several items though, the mileage per. item is gradually decreasing. This type of statistic can thus be interesting to investigate closer, in order to optimize how many items each picking order list should contain in order to minimize the mileage per picked item.
另一個有趣的統(tǒng)計數字，顯示了相同的趨勢，是右圖中每個被拾取項目的行駛距離分布。 在這里，我們看到，對于揀選清單少的物品，每英里的典型行駛里程。 物品相對較高(差異很大，取決于一些物品位于同一走廊等情況下的“幸運”程度)。 對于帶有多個項目的揀貨清單，每英里的里程數。 項目正在逐漸減少。 因此，為了進一步優(yōu)化每個揀貨訂單列表應包含的物品數量，以使每個揀選物品的里程數最小化，這種統(tǒng)計數據可能會更有趣地進行深入研究。
Estimating driving distance per list/item vs. number of items per list.估算每個列表/項目的行駛距離與每個列表的項目數。Example 2: Here I have used real-world data that also contains additional information in the form of a customer ID (here shown for only two customers). We can then take a closer look at the distribution in mileage per. picking order list for the two customers. For example, do you typically have to drive longer distances to pick the goods of one customer versus another? And, should you charge that customer extra for this additional cost?
示例2：在這里，我使用了真實數據，其中還包含客戶ID形式的附加信息(此處僅針對兩個客戶顯示)。 然后，我們可以仔細查看每公里里程的分布。 挑選兩個客戶的訂單清單。 例如，您通常需要開車較長距離來挑選一位客戶與另一位客戶的商品嗎？ 而且，您是否應該向該客戶額外收取這筆額外費用？
The below figure to the left shows the distribution in mileage for ?Customer 1? and ?Customer 2? respectively. One of the things we can interpret from this is that for customer 2, most picking order lists have a noticeably shorter driving distance compared to customer 1. This can also be shown by calculating the average mileage per. picking order list for the two customers (figure to the right).
左下圖分別顯示了“客戶1”和“客戶2”的里程分布。 我們可以從中得出的解釋之一是，對于客戶2，大多數揀貨訂單列表的行駛距離比客戶1短得多。這也可以通過計算每人的平均里程來顯示。 兩個客戶的揀貨訂單清單(右圖)。
This type of information can e.g. be used to implement pricing models where the product price to the customer is also based on mileage per order. For customers where the order involves more driving (and thus also more time and higher cost) you can consider invoicing extra compared to orders that involve short driving distances.
此類信息可以例如用于實施定價模型，其中對客戶的產品價格也基于每個訂單的里程。 對于訂單涉及更多駕駛(因此也需要更多時間和更高成本)的客戶，您可以考慮比涉及短途駕駛距離的訂單多開票。
摘要： (Summary:)
In the end, I hope I have convinced you that graph theory is not just some abstract mathematical concept, but that it actually has many useful and interesting applications! Hopefully, the examples above will be useful for some of you in solving similar problems later, or at least satisfy some of your curiosity when it comes to graph theory and some of its applications.
最后，我希望我已經說服了您，圖論不僅是一些抽象的數學概念，而且它實際上具有許多有用且有趣的應用程序！ 希望上面的示例對某些人在以后解決類似問題時很有用，或者至少滿足您對圖論及其某些應用的好奇。
The cases discussed in the article covers just a few examples that illustrate some of the possibilities that exist. If you have previous experience and ideas on the topic, it would be interesting to hear your thoughts in the comments below!
本文討論的案例僅涵蓋了一些示例，這些示例說明了存在的一些可能性。 如果您以前有關于該主題的經驗和想法，那么在下面的評論中聽聽您的想法會很有趣！
Did you find the article interesting? If so, you might also like some of my other articles on topics such as AI, Machine Learning, physics, etc., which you can find here: https://medium.com/@vflovik
您覺得這篇文章有趣嗎？ 如果是這樣，您可能還會喜歡我的其他一些有關AI，機器學習，物理等主題的文章，您可以在這里找到： https : //medium.com/@vflovik
翻譯自: https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2
圖論為什么這么難
總結
以上是生活随笔為你收集整理的图论为什么这么难_图论是什么，为什么要关心？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于kb的问答系统_1KB以下基于表的Q
- 下一篇： 价外费用含税吗