1 Topic by denisko

  • denisko
  • Member
  • Offline
  • Registered: 2008-09-05
  • Posts: 4,849

Topic: The task of the direct-sales representative with storage.

Colleagues, there was such strange question. Whether it is possible to reduce to the task of the direct-sales representative the task at which costs function depends on a way, for example a scoring maximum if between a point of a route And and a point of route B it has been transited exactly N nodes? If it is possible, as? Basically, as far as I understand, is (whether there is) the turbid decision to do N copies of the initial graph and at visiting of everyone  points to pass from a copy to a copy (as it in . becomes), but can eat a method easier?

2 Reply by alpha21264

  • alpha21264
  • Member
  • Offline
  • Registered: 2006-08-07
  • Posts: 24,335

Re: The task of the direct-sales representative with storage.

Hello, denisko, you wrote: D> Colleagues, there was such strange question. Whether it is possible to reduce to the task of the direct-sales representative the task at which costs function depends on a way, for example a scoring maximum if between a point of a route And and a point of route B it has been transited exactly N nodes? If it is possible, as? Well allow to dance from an oven (Whip). The task  dares a method of branches and boundaries. Guessed, or still helps are necessary?

3 Reply by denisko

  • denisko
  • Member
  • Offline
  • Registered: 2008-09-05
  • Posts: 4,849

Re: The task of the direct-sales representative with storage.

Hello, alpha21264, you wrote: A> Well allow to dance from an oven (Whip). A> the Task  dares a method of branches and boundaries. A> Guessed, or still helps are necessary? , here not a policy, here it is necessary to read. It is not necessary for me _ _, it is necessary for me __.

4 Reply by denisko

  • denisko
  • Member
  • Offline
  • Registered: 2008-09-05
  • Posts: 4,849

Re: The task of the direct-sales representative with storage.

Hello, Tyomchik, you wrote: Those> Perhaps minizinc - it that is necessary for you for the description of restrictions "strictly N nodes" and to try to feed it in op-tools? Unsubscribe  if something acceptable turns out. Listen, at me the more academic or semiacademic interest. Though if to the writing hands business reaches, I will unsubscribe certainly. Anyway, thanks for .

5 Reply by alpha21264

  • alpha21264
  • Member
  • Offline
  • Registered: 2006-08-07
  • Posts: 24,335

Re: The task of the direct-sales representative with storage.

Hello, denisko, you wrote: D> Hello, alpha21264, you wrote: A>> Well allow to dance from an oven (the Whip). A>> the Task  dares a method of branches and boundaries. A>> Guessed, or still helps are necessary? D> Alfych, here not a policy, here it is necessary to read. It is not necessary for me _ _, it is necessary for me __. You please distinguish "task" and "method". The task is not reduced, because it is other task.  it is necessary to find a minimum of scales. And you need to find an optimum. You will not reduce.

6 Reply by kl

  • kl
  • Member
  • Offline
  • Registered: 2002-03-12
  • Posts: 2,434

Re: The task of the direct-sales representative with storage.

Hello, denisko, you wrote: to Reduce, certainly, it is possible. A question as I understand, in, whether it is possible to reduce in the polynomial image. As both tasks on columns, it is logical to think of transformation of the graph so that the task accepted standard for TSP a type. Most simple is to construct the multi-graph with the same peaks but in which the edge between And and Would correspond to a certain way between And and in the initial graph and has the same weight. Generally such convergence will not be natural polynomial since number of ways not , but probably at you it is possible to find certain restrictions in a condition of the initial task which make it possible. Well there, for example, there is only a polynomial number of various scales for all ways between And and, or something in such spirit.

7 Reply by NotImplemented

  • NotImplemented
  • Member
  • Offline
  • Registered: 2008-06-11
  • Posts: 69

Re: The task of the direct-sales representative with storage.

Hello, denisko, you wrote: D> Colleagues, there was such strange question. Whether it is possible to reduce to the task of the direct-sales representative the task at which costs function depends on a way, for example a scoring maximum if between a point of a route And and a point of route B it has been transited exactly N nodes? If it is possible, as? D> Basically, as far as I understand, is (whether there is) the turbid decision to do N copies of the initial graph and at visiting of everyone  points to pass from a copy to a copy (as it in . becomes), but can eat a method easier? Greetings, I correctly understand, what it is necessary to visit each peak of the graph exactly once, and on each step the edge weight depends on an amount of already visited peaks?

8 Reply by NotImplemented

  • NotImplemented
  • Member
  • Offline
  • Registered: 2008-06-11
  • Posts: 69

Re: The task of the direct-sales representative with storage.

Hello, NotImplemented, you wrote: NI> Hello, denisko, you wrote: D>> Colleagues, there was such strange question. Whether it is possible to reduce to the task of the direct-sales representative the task at which costs function depends on a way, for example a scoring maximum if between a point of a route And and a point of route B it has been transited exactly N nodes? If it is possible, as? D>> Basically, as far as I understand, is (whether there is) the turbid decision to do N copies of the initial graph and at visiting of everyone  points to pass from a copy to a copy (as it in . becomes), but can eat a method easier? NI> greetings, I correctly understand, what it is necessary to visit each peak of the graph exactly once, NI> and on each step the edge weight depends on an amount of already visited peaks? It, in general, not so is important. The task of the direct-sales representative - NP-full, therefore any task from class NP can be shown to it. The accessory of your task to class NP can be checked up on determination.