algorithm - Adding waypoints to A* graph search -

algorithm - Adding waypoints to A* graph search -

I have the ability to calculate the best route between a start and end point using A *. Right now, I add points between all the start and end points by applying A * to the pair in all the permutations of my points.

Example:

I want to get from point 1 to point 4. In addition, I want to pass points 2 and 3.

I compute the permutations of (1, 2, 3, 4):

  1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 Then, for each permutation, I first I calculate the A * route from one to the other, then the third to the third place, then from third to the third number. 
  When I calculate it for each permutation, then I fix the routes based on distance and at least return. 
  Obviously, this works, but it involves a lot of calculations and I have 6 ways (801 permutations items 40320: -)) 
  Doing this Better way?

  
  First of all, you should store all intermediate calculations. Once you calculate the route from 1 to 2, you should not do it again again, just look in a table. Second, if your article is unrestricted, the path between 2 to 1 is equal to the path from 1 to 2, so you should not resume it again. 
  And in the end, you have an algorithm in any case that is exponential for the number of digits required to pass by you. This journey is similar to the vendor's problem, and if you include all the available points, then it will actually be a problem. The problem is NP-complete, that is complexity in it, in the way the number of points are exponential. 
  So if you have a lot of points that you have to pass, the exponential collapse is inevitable.


















Get link





Facebook





X





Pinterest





Email





Other Apps




Comments





Post a Comment







Popular Posts




Unable to get a fresh ASP.NET MVC project running with Visual Studio
2008 -



    This is a very basic question. I'm asking this silly about this, but I'm stuck something else and hopefully That something here can save me some time. So I open VS2008, to download the new ASP.NET MVC web application and click OK I want to prepare a test project. I debug my new MVC project to hit F5 then I enable the debugging to the web. I choose to modify the config file. It goes where I get a page load error.   Firefox can not establish a connection to the server on the local host: 57323.   Do I have to do something special for Vista? Or I should do something with IIS   Thanks for helping a noob   6/30/2009 update   OK, I think that I VS2008 may need to be reinstalled with the ASP.NET Development Server port. I have tried to do everything that I have suggested. I've marked Default.aspx as the start page. I tried to open it in Firefox / IE 8 / and Chrome. I tried to uninstall / reinstall ASP.NET MVC, which was not working. I tried telnetting with Putin with a local ho...






delphi - Mouseover hint for TChart series value -



    I am using a TChart in Delphi 7, and I want to display charts sometime. I am using the following code to set the chain value to a database query:    chart1.FreeAllSeries; Chart1.SeriesList.Clear; Chart1.AddSeries (TBarSeries.Create (self)); TBarSeries (chart1.Series [0]) BarStyle :. = BsRectGradient; Stop starting with Query 1; Executed; While EOF does not start chart1.Series [0]. Add (field 'flags' ('sum_actual_days'), Field Astrstring ('contract_no')); the upcoming; End; End;    Each time (value) is now showing both the label below the bar and in a yellow rectangle above the bar.   Rather than repeating the amount of label twice, I have some additional information from the query that I would like to show above the bar rather than the label (or, preferably, as a mouseover signal). Can it be done with TChart? And how ...?      This can be done with a TChart using the onMouseMeave event of the chart. Something like this should start with you:    Process TForm...






sql - Incorrect syntax near the keyword 'table' -



    I'm getting this error what I'm doing is trying to get data from a table and a db and Keep it in another DB and table. The tables are not exactly the same, I am using a FETCH cursor, so I get the first line from the DB1 table and then keep each column value in the declared variable. Then I run an assembly statement in db2 table and get the next value. All of these are working properly because it runs properly, but in the end I get this error,   Wrong syntax near the keyword 'table'.   In the entire transaction details, an attempt / catch with the error of expression in the Cat block, apart from this, I do not know what is the reason for it.   Here is the code    added to prevent additional result set at SET NOCOUNT - Interfering with the SELECT statement. Set nosenate on; TRY begin transaction sets ITENDITY column off --TURN identity_insert [dB] start [dbo] [TEST] all CONSTRAINTS table --TURN [dB] change [dbo] [TEST] NOCHECK barrier All -.... Insert statement here @...








Powered by Blogger