 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 8 | 1/1 | 返回列表 |
| 查看: 2290 | 回復(fù): 7 | ||
gnss銅蟲 (正式寫手)
|
[求助]
30金幣求助：最長(zhǎng)路徑問題，要求遍歷每個(gè)節(jié)點(diǎn)，總路徑最長(zhǎng)
|
|
某地區(qū)150個(gè)地面點(diǎn)，每個(gè)點(diǎn)坐標(biāo)(x,y,z)，任意兩點(diǎn)i,j間組成基線，基線的長(zhǎng)度為L(zhǎng)(i,j)。 問題：找出一條路徑，要求： 1, 經(jīng)過每一個(gè)站點(diǎn)； 2, 每個(gè)站點(diǎn)可能不止使用一次； 3, 任何兩條基線不相關(guān)，即如果路徑含有i->j->k,則不允許存在i->k; 4 即該路徑含150個(gè)節(jié)點(diǎn)，149條互不相關(guān)的基線; 5, 對(duì)L(i,j)求和，要求總路徑最長(zhǎng)。 這是一個(gè)什么問題呢？暴力枚舉搞不定，計(jì)算量太大了。 30金幣求助一下。我同時(shí)也在學(xué)習(xí)中。 [ Last edited by gnss on 2012-6-12 at 15:07 ] |
回復(fù)此樓» 猜你喜歡
336求調(diào)劑
已經(jīng)有3人回復(fù)
-
286求調(diào)劑
已經(jīng)有3人回復(fù)
-
一志愿華中科技大學(xué)071000，求調(diào)劑
已經(jīng)有3人回復(fù)
-
279分求調(diào)劑 一志愿211
已經(jīng)有14人回復(fù)
-
332求調(diào)劑
已經(jīng)有3人回復(fù)
-
0856材料專碩353求調(diào)劑
已經(jīng)有3人回復(fù)
-
材料學(xué)學(xué)碩080502 337求調(diào)劑-一志愿華中科技大學(xué)
已經(jīng)有5人回復(fù)
-
085601調(diào)劑 358分
已經(jīng)有4人回復(fù)
-
0856 271求調(diào)劑
已經(jīng)有3人回復(fù)
-
能源材料化學(xué)課題組招收碩士研究生8-10名
已經(jīng)有15人回復(fù)
» 本主題相關(guān)價(jià)值貼推薦，對(duì)您同樣有幫助:
- 考博成功散點(diǎn)金幣
已經(jīng)有187人回復(fù)
- SCI再次投稿，先散6個(gè)金幣，攢人品，如果送審散66個(gè)金幣，如果接收散金IF*100
已經(jīng)有15人回復(fù)
- 求幫忙分析一下這三個(gè)紅外圖譜，謝謝。有【金幣】贈(zèng)送。。。。。
已經(jīng)有14人回復(fù)
- 塵埃落定，特散金幣100
已經(jīng)有208人回復(fù)
- 渤海鉆探創(chuàng)國內(nèi)水平段最長(zhǎng)紀(jì)錄
已經(jīng)有4人回復(fù)
- Euler 工程 第廿六題：最長(zhǎng)的循環(huán)節(jié)
已經(jīng)有9人回復(fù)
- Euler 工程 第14題：找最長(zhǎng)的數(shù)列
已經(jīng)有9人回復(fù)
- 100金幣求助CeF3：要求為國藥批號(hào)為F20060915的CeF3！
已經(jīng)有3人回復(fù)
- 20金幣求助兩句話漢譯英，急求，謝謝,謝絕軟件翻譯
已經(jīng)有3人回復(fù)
- 有比我更悲劇的嗎？說說你最長(zhǎng)審稿時(shí)間的一篇文章
已經(jīng)有40人回復(fù)
- 【交流】急，60金幣交流-考博,大家還在做實(shí)驗(yàn)嗎？復(fù)習(xí)到哪個(gè)階段了？
已經(jīng)有13人回復(fù)
- 【求助】25金幣求助：氧化鋁作為吸附劑的柱層析問題
已經(jīng)有19人回復(fù)
- 【求助】用DS2.5對(duì)接錯(cuò)誤(已經(jīng)自己解決，請(qǐng)退換金幣)
已經(jīng)有4人回復(fù)
- 【分享】保諾給解決戶口了，撒15個(gè)金幣
已經(jīng)有107人回復(fù)
2樓2012-06-12 15:52:33
libralibra
至尊木蟲 (著名寫手)
驃騎將軍
- 程序強(qiáng)帖: 40
- 應(yīng)助: 817 (博后)
- 金幣: 12914.1
- 紅花: 64
- 帖子: 2238
- 在線: 287.3小時(shí)
- 蟲號(hào): 696514
- 注冊(cè): 2009-02-05
- 專業(yè): 計(jì)算機(jī)軟件
3樓2012-06-13 02:12:25
dxwbucea
鐵蟲 (著名寫手)
- 應(yīng)助: 20 (小學(xué)生)
- 金幣: 17156.4
- 紅花: 1
- 帖子: 1722
- 在線: 80.4小時(shí)
- 蟲號(hào): 1586258
- 注冊(cè): 2012-01-24
- 專業(yè): 計(jì)算數(shù)學(xué)與科學(xué)工程計(jì)算
【答案】應(yīng)助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★
感謝參與，應(yīng)助指數(shù) +1
gnss: 金幣+10, 貨郎擔(dān)問題要求每個(gè)點(diǎn)只能使用一次，我的沒有這個(gè)限制 2012-06-13 19:10:34
感謝參與，應(yīng)助指數(shù) +1
gnss: 金幣+10, 貨郎擔(dān)問題要求每個(gè)點(diǎn)只能使用一次，我的沒有這個(gè)限制 2012-06-13 19:10:34
| 是圖論中的貨郎擔(dān)問題的變化，只需要選出一個(gè)比最長(zhǎng)的基站長(zhǎng)度還大的數(shù)M，用此數(shù)M分別減去每個(gè)基站長(zhǎng)度作為新的基站長(zhǎng)度，則轉(zhuǎn)化為標(biāo)準(zhǔn)的貨郎擔(dān)問題了。貨郎擔(dān)問題有算法求解。 |
4樓2012-06-13 07:49:51
5樓2012-06-13 07:54:54
smswt
鐵桿木蟲 (小有名氣)
- 應(yīng)助: 4 (幼兒園)
- 金幣: 6049.6
- 帖子: 112
- 在線: 362.5小時(shí)
- 蟲號(hào): 905964
- 注冊(cè): 2009-11-18
- 專業(yè): 光學(xué)
【答案】應(yīng)助回帖
★ ★ ★ ★ ★
感謝參與，應(yīng)助指數(shù) +1
gnss: 金幣+5, ★★★很有幫助, 您這個(gè)算法每個(gè)點(diǎn)只能使用一次，我的沒有這個(gè)限制 2012-06-14 08:37:01
感謝參與，應(yīng)助指數(shù) +1
gnss: 金幣+5, ★★★很有幫助, 您這個(gè)算法每個(gè)點(diǎn)只能使用一次，我的沒有這個(gè)限制 2012-06-14 08:37:01
|
沒學(xué)過圖論，看下這個(gè)方法可以不 1.把給的N個(gè)點(diǎn)分成兩個(gè)集合A，B 2.對(duì)有限集合，A，B之間點(diǎn)的距離肯定有一個(gè)最大值，把這個(gè)距離設(shè)成L(A,B) 現(xiàn)在實(shí)行算法如下： 1,讓A為空集，B為N所有點(diǎn)的集合，從B中任意選一個(gè)點(diǎn)放到A（不知道任意選對(duì)不對(duì)） 2，計(jì)算L(A,B)，找到A，B中對(duì)應(yīng)該距離的點(diǎn)（假設(shè)分別為i，j） 3.連接i->j，同時(shí)把j點(diǎn)從B中去掉，放入A中 4.重復(fù)2,3，直到B為空集 這種方法可以保證已經(jīng)有通路的點(diǎn)不會(huì)再連接，同時(shí)每次連接都找的是最大距離，應(yīng)該可以的到你要的結(jié)果，就是理論證明起來有點(diǎn)難 |
6樓2012-06-13 15:09:15
smswt
鐵桿木蟲 (小有名氣)
- 應(yīng)助: 4 (幼兒園)
- 金幣: 6049.6
- 帖子: 112
- 在線: 362.5小時(shí)
- 蟲號(hào): 905964
- 注冊(cè): 2009-11-18
- 專業(yè): 光學(xué)
7樓2012-06-14 10:41:33
 |
8樓2015-06-11 16:11:31
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 gnss 的主題更新
| 8 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 279分求調(diào)劑 一志愿211 +13 | chaojifeixia 2026-03-19 | 14/700 |
|
|---|---|---|---|---|
|
[考研] 346求調(diào)劑[0856] +4 | WayneLim327 2026-03-16 | 7/350 |
|
|
|
[考研] 311求調(diào)劑 +5 | 冬十三 2026-03-18 | 5/250 |
|
|
|
[考研] 一志愿武漢理工材料工程專碩調(diào)劑 +9 | Doleres 2026-03-19 | 9/450 |
|
|
|
[考研] 本人考085602 化學(xué)工程 專碩 +19 | 不知道叫什么！ 2026-03-15 | 21/1050 |
|
|
|
[考研] 295材料求調(diào)劑，一志愿武漢理工085601專碩 +5 | Charlieyq 2026-03-19 | 5/250 |
|
|
|
[考研] 一志愿西安交通大學(xué) 學(xué)碩 354求調(diào)劑211或者雙一流 +3 | 我想要讀研究生 2026-03-20 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +3 | @taotao 2026-03-20 | 3/150 |
|
|
|
[考研] 08工學(xué)調(diào)劑 +5 | 用戶573181 2026-03-20 | 5/250 |
|
|
|
[考研] 材料學(xué)碩318求調(diào)劑 +5 | February_Feb 2026-03-19 | 5/250 |
|
|
|
[考研]
 0854，計(jì)算機(jī)類招收調(diào)劑
+3
|
胡辣湯放糖 2026-03-15 | 6/300 |
|
|
|
[考研] 334求調(diào)劑 +3 | 志存高遠(yuǎn)意在機(jī)?/a> 2026-03-16 | 3/150 |
|
|
|
[考研] 290求調(diào)劑 +3 | p asserby. 2026-03-15 | 4/200 |
|
|
|
[考研] 一志愿蘇州大學(xué)材料工程（085601）專碩有科研經(jīng)歷三項(xiàng)國獎(jiǎng)兩個(gè)實(shí)用型專利一項(xiàng)省級(jí)立項(xiàng) +6 | 大火山小火山 2026-03-16 | 8/400 |
|
|
|
[考研] 283求調(diào)劑 +3 | 聽風(fēng)就是雨； 2026-03-16 | 3/150 |
|
|
|
[考研] 機(jī)械專碩325，尋找調(diào)劑院校 +3 | y9999 2026-03-15 | 5/250 |
|
|
|
[考研] 304求調(diào)劑 +4 | ahbd 2026-03-14 | 4/200 |
|
|
|
[考研] 277材料科學(xué)與工程080500求調(diào)劑 +3 | 自由煎餅果子 2026-03-16 | 3/150 |
|
|
|
[考研] 本科南京大學(xué)一志愿川大藥學(xué)327 +3 | 麥田耕者 2026-03-14 | 3/150 |
|
|
|
[考研] 復(fù)試調(diào)劑 +3 | 呼呼？~+123456 2026-03-14 | 3/150 |
|