在做數學最短路徑問題時，要用到對稱法，那麼我到底應該做哪個點

1樓：匿名使用者

通常人們的思維習慣是做後面那個點的對稱點，可能是老師下意識的認為正確答案只有乙個吧。為了考試，那你可以按照一般人的思路，說了有兩個點，那就做後面乙個的對稱點（其實都沒有什麼關係的，你要不找一下老師問一下錯在**，有可能是你其他地方寫錯了呢）

在做數學最短路徑問題時，要用到對稱法，那麼我到底應該做哪個點的對稱點呢？

2樓：匿名使用者

你好，作a或b關於l的對稱點都可以。

ab'就是最短路徑的長，此時bp+ap=bp'+ap=ab'最短

數學最短路徑問題最方便的解法是什麼

3樓：4399賽爾號

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」

，有時被簡稱作「路徑演算法」。最常用的路徑演算法有： dijkstra 演算法、 a*演算法、 spfa 演算法、 bellman-ford 演算法和 floyd-warshall 演算法，本文主要介紹其中的三種。

最短路徑問題是圖論研究中的乙個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。演算法具體的形式包括：確定起點的最短路徑問題：

即已知起始結點，求最短路徑的問題。確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。

在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

全域性最短路徑問題：求圖中所有的最短路徑。 floyd 求多源、無負權邊的最短路。

用矩陣記錄圖。時效性較差，時間複雜度 o(v^3)。 floyd-warshall 演算法（floyd-warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題。

floyd-warshall 演算法的時間複雜度為 o(n^3)，空間複雜度為 o(n^2)。 floyd-warshall 的原理是動態規劃：設 di,j,k 為從 i 到 j 的只以(1..

k)集合中的節點為中間節點的最短路徑的長度。若最短路徑經過點 k，則 di,j,k = di,k,k-1 + dk,j,k-1；若最短路徑不經過點 k，則 di,j,k = di,j,k-1。因此，di,j,k = min(di,k,k-1 + dk,j,k-1 , di,j,k-1)。

在實際演算法中，為了節約空間，可以直接在原來空間上進行迭代，這樣空間可降至二維。 floyd-warshall 演算法的描述如下： 1.

for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.

if (di,k + dk,jo（e*lgv）。當是稀疏圖的情況時，此時 e=v*v/lgv，所以演算法的時間複雜度可為 o（v^2）。若是斐波那契堆作優先佇列的話，演算法時間複雜度，則為 o（v*lgv + e）。

bellman-ford 求單源最短路，可以判斷有無負權迴路（若有，則不存在最短路），時效性較好，時間複雜度 o（ve）。 bellman-ford 演算法是求解單源最短路徑問題的一種演算法。單源點的最短路徑問題是指：

給定乙個加權有向圖 g 和源點 s，對於圖 g 中的任意一點 v，求從 s 到 v 的最短路徑。與 dijkstra 演算法不同的是，在 bellman-ford 演算法中，邊的權值可以為負數。設想從我們可以從圖中找到乙個環路（即從 v 出發，經過若干個點之後又回到 v）且這個環路中所有邊的權值之和為負。

那麼通過這個環路，環路中任意兩點的最短路徑就可以無窮小下去。如果不處理這個負環路，程式就會永遠執行下去。而 bellman-ford 演算法具有分辨這種負環路的能力。

spfa是 bellman-ford 的佇列優化，時效性相對好，時間複雜度 o（ke）（k<

所不同的是，spfa 演算法通過維護乙個佇列，使得乙個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重複的操作次數。 spfa 演算法可以用於存在負數邊權的圖，這與 dijkstra 演算法是不同的。與 dijkstra 演算法與 bellman-ford 演算法都不同，spfa 的演算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。

在最好情形下，每乙個節點都只入隊一次，則演算法實際上變為廣度優先遍歷，其時間複雜度僅為 o(e)。另一方面，存在這樣的例子，使得每乙個節點都被入隊(v-1)次，此時演算法退化為 bellman-ford 演算法，其時間複雜度為 o(ve)。 spfa 演算法在負邊權圖上可以完全取代 bellman-ford 演算法，另外在稀疏圖中也表現良好。

但是在非負邊權圖中，為了避免最壞情況的出現，通常使用效率更加穩定的 dijkstra 演算法，以及它的使用堆優化的版本。通常的 spfa 演算法在一類網格圖中的表現不盡如人意。

4樓：李浩天

dijkstra演算法

dijkstra

演算法又稱為單源

最短路徑，所謂單源是在乙個有向圖中，從乙個頂點出發，求該頂點至所有可到

達頂點的最短路徑問題。

設g=（v，e）是乙個有向圖，v表示頂點，e表示邊。它的每一條邊（i，j）屬於e，都有乙個非負權w（i,j），在g中指定乙個結點v0，要求把從v0到g的每乙個接vj（vj屬於v）的最短有向路徑找出來（或者指出不存在）。

dijstra

演算法是運用貪心的策略，從源點開始，不斷地通過相聯通的點找出到其他點的最短距離

基本思想是：

設定乙個頂點的集合s，並不斷地擴充這個集合，乙個頂點屬於集合s當且僅當從源點到該點的路徑已求出。開始時s中僅有源點，並且調整非s中點的最短路徑長度，找當前最短路徑點，將其加入到集合s，直終點在s中。

基本步驟：

1、把所有結點分成兩組：

第一組：包括已經確定最短路徑的結點；

第二組：包括尚未確定最短路徑的結點。

2、開始時，第一組只包含起點，第二組包含剩餘的點；

3、用貪心的策略，按最短路徑長度遞增的順序把第二組的結點加到第一組去，直到v0可達的所有結點都包含於第一組中。在這個過程中，不斷更新最短路徑，總保持從v0到第一組各結點的最短路徑長度dist都不大於從v0到第二組任何結點的路徑長度。

4、每個結點對應乙個距離值，第一組結點對應的距離就是v0到此結點的最短路徑長度，第二組結點對應的距離值就是v0由第一組結點到此結點的最短路徑長度。

5、直到所有的頂點都掃瞄完畢（v0可達的所有結點都包含於第一組中），找到v0到其它各點的所有最短路徑。

5樓：花樹下de流年

過某一直線（稱作y）做對稱點，連線對稱點與另一點，與y的交點為所求

6樓：匿名使用者

兩點之間，線段最短？

數學最短路徑問題，哪個大神能教會我這道題，過程

7樓：

在ab上取一點p，並且做mp⊥np，所以三角形mpn為直角三角形。

因為∵mpn是直角三角形

所以∴mp+np=mn

所以∴mp+np+2mpnp=mn+2mpnp∴(mp+np)=mn+2mpnp

如果p為ab上任意一點，連線mp，np那麼三角形mpn為任意三角形。那麼根據三角形任意兩邊之和大於第三邊。則有，mp+pn＞mn

所以∴(mp+pn)＞mn

所以∴直角三角形(mp+np)=mn+2mpnp任意三角形(mp+np)＞mn

可以理解為直角三角形第三邊加上2mpnp都沒有任意三角形第三邊長，所以，直角三角形最短

8樓：好學生你麻痺

做m關於ab的對稱點m'，連線m'n，線m'n與ab交點就是p。因為兩點之間線段最短

9樓：莪告別懵懂

做m關於ab的對稱點m'，連線nm'交ab於p點，mnp即為所求

求最短路徑問題都說軸對稱最短，軸對稱最短是什麼意思呀？

10樓：維翎兒

理論上說軸對稱是最短距離其實不是，科學的最短距離是0才是，使2點重合就是最短距離軸對稱是數學上說，0是空間說

11樓：樂觀的雲中游

最短路徑應該是直線。0距離不成立。

如何畫最短路徑是否畫對稱點

12樓：洋哥丶不二情

如圖所示，假如求a點到b點最短距離，可以作b的對稱點b1，連線ab1交直線於點c,那麼acb為最短路徑

如果可以幫助你，請給好評，謝謝

八年級上冊數學題，關於最短路徑問題

13樓：千尋

把on放水平，以on為x軸，建立二維直角座標系，已知a,b座標，p的座標設為（x，0），列出方程可以求得結果。

初中數學函式中的對稱點問題應該怎麼做

14樓：清水竹聯

對於平面直角座標下的電（x,y)關於點（a,b)的對稱點平面內一點(x,y)關於(a,b)對稱的點的座標為（2a-x,2b-y）

解設點(x,y)關於(a,b)對稱的點為（m,n）∴點（m,n）為點(x,y)和點(a,b)的中點∴a=（x+m）/2

b= （y=n ）/2

∴m=2a-x

n=2b-y

∴平面內一點(x,y)關於(a,b)對稱的點的座標為（2a-x,2b-y）

在做數學最短路徑問題時，要用到對稱法，那麼我到底應該做哪個點

解決路線最短問題的依據是？最短路線問題

下圖中，從A沿實線走最短路徑到B點，共有多少種走法

初中數學最短距離問題，初中數學最短距離問題

在做數學最短路徑問題時，要用到對稱法，那麼我到底應該做哪個點

解決路線最短問題的依據是？最短路線問題

下圖中，從A沿實線走最短路徑到B點，共有多少種走法

初中數學最短距離問題，初中數學最短距離問題

相關推薦